Hello everyone!
So, the problem is to find all prime numbers on segment N .. N+M where 1010 <= N <= 1011 and 1 <= M <= 105.
My algorithm with O(M * sqrt(K)) asymptotic, where K — is the number that we are testing for primality exceeds TL.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
Hello everyone!
So, the problem is to find all prime numbers on segment N .. N+M where 1010 <= N <= 1011 and 1 <= M <= 105.
My algorithm with O(M * sqrt(K)) asymptotic, where K — is the number that we are testing for primality exceeds TL.
Name |
---|
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 ) .
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 106 (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