Смотри. Берешь какие-нибудь простые числа. Много простых чисел.
Например, все до 10^6.
И просеиваешь ими как в обычном решете Эратосфена свои числа от N до N+M.
Все. xD

Кстати. /blog/entry/14874.

Вроде бы, недавно был уже блог. Просто ищешь все простые числа до sqrt(N+M); Ищем за O(1000000);

bool pr[1000500];
vector<int> p;
void prime(int n=1000000){
    for(int i=4;i<=n;i+=2){
        pr[i]=1;
    }
    p.push_back(2);
    for (int i=3;i<=n;i+=2){
        if (!pr[i]){
            p.push_back(i);
            for (int j=i*i;j<=n;j+=2*i){
                pr[j]=1;
            }
        }
    }
}

как то так. А потом решетом проходишься с н до м, и убираешь числа делящие на одно из этих простых.

for (int i=0;i<p.size();i++){
  //t = минимальное число, чтобы при уможение на p[i] было число между n и m 
  //t не должен быть равен одному
  for(int j=p[i]*t; j<=n+m; j+=p[i]){
      //число j не простое
  }
}

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 ) .

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

Firstly, generate all of primes between 1 and 10⁶ (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?

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.

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

Мб тест Ферма поможет?

Извиняюсь за некропостинг, новый топик создавать не захотел, так как вопрос незначителен и с этой темой связан.

Может кто помочь найти задачу на КФе, где нужно строить решето Эратосфена на интервале [L, R]. Точно помню что такая была на каком-то контесте, а вот найти не смог. Также буду благодарен задачам, где используется функция Эйлера.

п.с. Задача нужна именно на КФе, чтоб её потом можно было добавить в мэшап.