OJ Board

say i have to find out whether a=2^31 is prime or not.
but i cant do it by testing if a is divided by the primes between sqrt(a),cause it results in TLE.what should i do then?

is there any efficient method to find primes within a range?can we use seive to find primes in [a,b] ?i mean we should not start seive from 2 but from later numbers.

Yes it is possible to do sieve in a segment .. which is better known as segmented sieve ..........it keeps a linear array and the first element array[0] is the sieve result of [Lower Limit + index ] . if we want to do sieve in [a,b] , let us assume the linear array where we r gonna do sieve is X .. then X is is prime means number (a + i ) is prime .....

if u want . i can PM u the algorithm

Bye
Riyad

thankx riyad.
I already code it.I solved 10140-prime distance using segment seive.but am getting WA.can you give me some sample input/output for 10140?

thankx riyad.
I already code it.I solved 10140-prime distance using segment seive.but am getting WA.can you give me some sample input/output for 10140?

Input:
[cpp]
0 17
1 17
2 17
17 18
32 36
2 5
16 19
2146483647 2147483647
3 5
[/cpp]
Output:
[cpp]
5,7 are closest, 7,11 are most distant.
2,3 are closest, 7,11 are most distant.
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.
There are no adjacent primes.
2,3 are closest, 3,5 are most distant.
17,19 are closest, 17,19 are most distant.
2146483811,2146483813 are closest, 2146841093,2146841273 are most distant.
3,5 are closest, 3,5 are most distant.
[/cpp]

got accepted.thankx

Riyad or somebody else! I didnt understand the explaination. Would realy appreciate if someone sent me docs on the subject, or just explain how it works.
About a month ago I was aplying for a job, and one of their tasks was "Print all the prime numbers between A and B". My implementation was really stupid (what a shame ) , I simply re-wrote the standart Borland C exaple in Perl (they wanted me to do it in Perl) and turned the tasks in.
So, they never invited me for an interview. But I d really like to know how this segmented sieve works.

[c]
gen_all_primes_up_to[sqrt(B)] (using normal sieve)
isprime = new array of size B-A+1
initialize all elements of isprime to 1
for (i=0;i<primes_array_size;i++) {
start = (A/primes);
if (start*primes < A) start++;
if (start==1) start++; // don't mark prime as composite!!!
for (j=start*primes-A;j<B-A+1;j+= primes) isprime[j] = 0;
}
for (i=0;i<B-A+1;i++) if (isprime) print out A+i
[/c]

that's what a segmented sieve looks like to mark all primes in [A,B]
of course there are some clear optimizations that can be made concerning
even numbers

Thanks! That surely was clear enough. Me be smarter now.

hi ,
my segmented sieve code looks some thing like this .. its not hard to understand .. i guess so

[cpp]
long int L , U ,d ;
bool flag[10000005];
bool cool ;


void DoSieve(){

long int i , j ,ulim;

d = U - L +1 ;

for (i=0;i<d;i++) { flag=true;}

if ((L%2)==0) i=L ;
else i=L+1;
i=i-L;
for (;i<d;i+=2) { flag=false; }

ulim =(long) sqrt( U);
for (i=3;i<=ulim;i+=2) {
if (i>L && !flag[i-L]) continue;


j=L/i*i;


if (j<L) j+=i;
if (j==i) j+=i;

j-=L;
for (;j<d;j+=i) flag[j]=false;
}

if (L<=1) flag[1-L]=false;
if (L<=2) flag[2-L]=false;

}
[/cpp]

Thanks.
It seems like I'm gonna get that job!!!