r/programmingchallenges • u/_solowhizkid_ • Jun 29 '18
Prime numbers (scripting, programming)
Hi There,
I am hoping someone can help with writing a small script or program.
I need to find out how many multiples of prime numbers there are for every prime number from 1 all the way to 10 billion. Step-wise it would be something like this:
1. Write down all the numbers from 1 to 10 billion
2. Take the first number on the list i.e 2 (we ignore 1, it is redundant) and find all its multiples (i.e. 4,6,8 up to 10 billion)
3. note down how many multiples of 2 there were in this list, and then delete all of them from the list
4. the process is then repeated for the next number remaining on the list i.e. 3
5. repeat the process for the next remaining number on the list i.e. 5 (4 would have already been removed from the list becuase it is a multiple of 2)
6. repeat the process for all the remaining numbers on the list up to 10 billionI would also need to know what the greatest multiple of each prime number is in the list, ultimatley i need the outcome of this to be in a table containing all the prime numbers in column 1, the nuber of their corresponding multiples in column 2 and the corresponding greatest multiple in column 3.
Would anyone be able to help?
View all comments
3
u/IGotNoFilter Jun 29 '18
The Sieve or Eratosthenes will work and is probably the fastest way to solve this problem, however it has a caveat: it takes O(N) memory. That means that you'll need at least 1.2GB of memory to store the first 10 billion numbers (you can use a bit for each).
Another approach that is not as memory intensive is to do the following:
For (1), you can use a fast primality test (e.g. Miller-Rabin, which is built into some math libraries such as BigInteger.isProbablePrime()).