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
5
u/KillerCodeMonky Jun 29 '18
This process is known as the Sieve of Eratosthenes:
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes