### Azret's blog

By Azret, 5 years ago, translation, ,

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.

• +7

 » 5 years ago, # |   +3 Have you tried segmented sieving method for the problem?
 » 5 years ago, # |   0 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.CodeMaybe this can get TLE if limit is strict as SPOJ , if this ocurrs you need to think in procesing primes <= sqrt( 10 ^ 11 ) .
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 You actually can use only four iterations with 100% correct result when N ≤ 1012 — see Wikipedia. Also you can multiply numbers with modulo less than 1012 using O(1) operations. long long multiply(long long a,long long b,long long m) { long long a1=a>>20; long long a2=a&1048575; long long b1=b>>20; long long b2=b&1048575; return (a2*b2 + ((a1*b2+a2*b1)<<20) + ((a1*b1<<20)%m<<20))%m; } And that means you only use per number.
 » 5 years ago, # | ← Rev. 4 →   0 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?
•  » » 5 years ago, # ^ |   +1 Yeah you are right. Here is the code
 » 5 years ago, # |   0 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
 » 4 years ago, # |   0 sieve of eratosthenes