Dream_Coder10's blog

Prime number in range 1 to 10^12!!!
By Dream_Coder10, history, 3 years ago, In English

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

  • Vote: I like it
  • -29
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Then what will be the solution of this problem?

    https://paste.ubuntu.com/p/TGd3NrfJS8/

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Do you have a public link to this problem instead of some very suspicious pastebin link? I don't want to help cheaters cheat in ongoing contests.

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Bruh, you literally said something else than this problem.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you explain me why do you think so?

        Never mind, I am just a beginner & trying to learn algorithm by implementing or debugging them...I would be very grateful to you if you help me to solve this probelm.....

        Thanks!

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Checking if a number is a prime or not can be made with Miler's Rabin in $$$O(log_2(N))$$$. So, getting 10,000 primes can be reasonable in that problem by just brute force+ Miler's Rabin(not sure though as big numbers tend to have less prime numbers in a range). But it might just pass.

          → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Depend on what you need the sieve for, sieving above $$$10^7$$$ for a problem is not recommended

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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)

→ Reply