I know that you can use sieve of Eratosthenes for finding all prime numbers in (1,N) interval, but can you suggest algorithm that can do that for (N,M) interval, when N,M are large, for instance 10^9 and N=500,000,000; M=501,000,000.
№ | Пользователь | Рейтинг |
---|---|---|
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 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
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 |
I know that you can use sieve of Eratosthenes for finding all prime numbers in (1,N) interval, but can you suggest algorithm that can do that for (N,M) interval, when N,M are large, for instance 10^9 and N=500,000,000; M=501,000,000.
Название |
---|
If the difference between N and M is less (about 10^5), then a modified sieve will work.
You need to cancel out all multiples of 2, 3, 5, and so on upto prime just less than or euqal to sqrt(M).
Are you talking about this problem?
Yes
Hi, you could search about segmented sieve, look this problem http://goo.gl/6nlsFP and its respective editorial http://goo.gl/oAjzCT both resources belong to codeforces user lbv, I hope that this has been helpful.
Find all prime numbers between 1 and sqrt(10^9), and for all numbers between m and n look by sieve, all numbers that divisible for this primes(except this primes) is not prime. Аsymptotic will be O(N(log(log(N)))+(n-m)*mehrunesartem(n-m)). If you want, I can write pseudocode.
I solved it in
, where K = M - N
If there's no divisor of X, which is not greater than
, then, there's no divisor, which is greater than
, so X is prime.
Can you explain how you do it?
I think it will be TLE.
Hmm, then I'm not sure :)
Actually, I think that was O(TKlogM). Half of all numbers divide by 2, 1/3 divide by 3, etc.
I know, that in java there is method n.nextProbablePrime(), that find first prime number after n and it's complexity is like O(n^(1/3)), but I don't know, how it works.
You can use the Miller-Rabin test, which applies Fermat's Little Theorem to test whether a number is prime. So if we're given n, the number we're testing, we write n - 1 = 2ab, and take some integer k and look at kb, k2b, k4b and so on up to k2ab, all modulo p. If we ever have a residue not equal to ± 1 that squares to become 1 modulo p, we know n can't be prime. This is because if p were prime and x2 ≡ 1 modulo p, then x ≡ ± 1 modulo p. More details can be found in the second half of this PDF.
If the numbers we are all testing are less than 4.7 billion, it suffices to test k = 2, 7, 61, according to this page. And for each test, we can do exponentiation by squaring to get all the needed powers of k in
time. So each primality test can be done
time, which should be fast enough for the problem. (They usually call Rabin-Miller a
time algorithm, but I'm pretty sure that's only after considering implementing bignum multiplication, which we don't have to do because we can just use long long's for everything).
Also, look at this.