Hello everyone!

So, the problem is to find all prime numbers on segment *N .. N+M* where *10*^{10}* <= N <= 10*^{11} and *1 <= M <= 10*^{5}.

My algorithm with *O(M * sqrt(K))* asymptotic, where *K — * is the number that we are testing for primality exceeds TL.

Have you tried segmented sieving method for the problem?

You can test if a number is prime with probabilistic methods as miller-rabin if i'm not wrong you can get O( it * log(n)^3 ) with it = number of iterations (with values near to 10^11 use 14) , in java is isProbablePrime with bigIntegers.

Code

Maybe this can get TLE if limit is strict as SPOJ , if this ocurrs you need to think in procesing primes <= sqrt( 10 ^ 11 ) .

N≤ 10^{12}— see Wikipedia.^{12}usingO(1) operations.And that means you only use per number.

Why don't we just use a similar algorithm with Eratosthene sieve?

Firstly, generate all of primes between 1 and 10

^{6}(actually )Second, create an array of bool, b[0..M]. b[i] = false if i+n hasn't been removed.

For each prime numbers in first step, try to clear all of its multipliers between N and N+M, then mark it onto array b.

This algorithm has the same complexity with Eratosthene sieve, isn't it?

Yeah you are right. Here is the code

You could use Eratosthene sieve,as some guys said. Also you can use Fermat law,which says that if p is prime then a^(p-1) MOD p = 1 1<a<p. The more a you take to test,the more sure it is that p is prime. Also to do the expontation you dont need to run it in O(N). You can use binary expontation right to left,which "break" the expontation into binary. For example if you have 5^5,because of 5=101(binary),the expontation will be 5^5=5^1+5^4.

here is wiki: http://en.wikipedia.org/wiki/Fermat_primality_test http://en.wikipedia.org/wiki/Modular_exponentiation

sieve of eratosthenes