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..!!
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.
Then what will be the solution of this problem?
https://paste.ubuntu.com/p/TGd3NrfJS8/
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.
Bruh, you literally said something else than this problem.
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!
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.
With 30 minutes or more, you will get all primes from that range with this implementation
Depend on what you need the sieve for, sieving above $$$10^7$$$ for a problem is not recommended
Easy.. sieve + window (similar to sliding window but here static)
Assumptions.. in 100*k numbers there will be atleast k prime numbers
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)
Can you implement that? I don't think that will work in 1sec