Блог пользователя Dream_Coder10

Автор Dream_Coder10, история, 6 лет назад, По-английски

How can I generate all prime numbers in range 1-10^12...

==================

I Tried with segmeted sieve, but I am not getting values over 10^6... Please give me the instructions or the modified segmented sieve code(it will be really helpful if you give me the code) so that I can learn by debugging it..!!

Problem => https://paste.ubuntu.com/p/TGd3NrfJS8/

Thanks in Advance..!!

  • Проголосовать: нравится
  • -29
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +31 Проголосовать: не нравится

You can't. There are around $$$\frac{10^{12}}{\ln(10^{12})} \approx 3.62 \cdot 10^{10}$$$ primes under $$$10^{12}$$$. And $$$3.62 \cdot 10^{10}$$$ is far too much memory to store in an array.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

With 30 minutes or more, you will get all primes from that range with this implementation

»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

Easy.. sieve + window (similar to sliding window but here static)

Assumptions.. in 100*k numbers there will be atleast k prime numbers

  • step1: precompute prime numbers upto 10^6 and store them as a list or array of prime numbers.
  • step2: take a window of numbers around n of size 100*k. that is n-100*k to n. and map it in an array as index... like index 0 is n-100*k+1, 1 is n-100*k+2, .............. k is n.
  • step3: interate through prime numbers less than sqrt(n)
    • step3(a): find lowest number greater than n-100*k which is divisible by that prime number(simple algebra)
    • step3(b): iterate from that number to n, incrementing by the selected prime number (Just like sieve) and mark in the array as not prime.
  • step4. Now array is computed. iterate from n in reverse direction until you find k primes less than equal to n from the array.

COMPLEXITY ANALYSIS :)

  • TIME COMPLEXITY: O(1e6*log(1e6))+O(100k*log(100k))+O(100k)=O(1e6*log(1e6))= O(2*1e7) takes less than 1 sec.

  • SPACE COMPLEXITY: O(1e6+{no of primes under 1e6}+100*k) basically O(2*1e6) which is less than 512MB

HOPE IT HELPS!

These is another method: using prime test in O(logn*100k)