Finding primes up to high numbers

 Posts: 3
 Joined: Sat May 16, 2015 3:43 pm
Finding primes up to high numbers
Hi everybody,
i registered here today, because i am struggling with an problem from project euler.
Scince i am not a native speaker, please forgive some typos or grammar mistakes .
Of course i can guess, that a direct discussion of the problems is not wanted so i will try to keep it general.
I tried to solve a harder problem (501) and i already have an idea for a solution. But this solution would require that i get a list of all primes from 2 to 10^12.
I managed to optimize my prime finding programm and now it gives me the primes from 2 to 10^6 in around 2.5 seconds. But you can imagine that it takes much to long for 10^12. So my idea was to put in a primetest like MillerRabin prime test, so that i only proof the numbers which are with a higher propability prime.
But acutally this slowed down the complete programme.
Of course i am not asking for the solution to the problem: i only want to ask, if its possible to calculate these numbers in a moderate time or if i am totally abroad with my ansatz.
i registered here today, because i am struggling with an problem from project euler.
Scince i am not a native speaker, please forgive some typos or grammar mistakes .
Of course i can guess, that a direct discussion of the problems is not wanted so i will try to keep it general.
I tried to solve a harder problem (501) and i already have an idea for a solution. But this solution would require that i get a list of all primes from 2 to 10^12.
I managed to optimize my prime finding programm and now it gives me the primes from 2 to 10^6 in around 2.5 seconds. But you can imagine that it takes much to long for 10^12. So my idea was to put in a primetest like MillerRabin prime test, so that i only proof the numbers which are with a higher propability prime.
But acutally this slowed down the complete programme.
Of course i am not asking for the solution to the problem: i only want to ask, if its possible to calculate these numbers in a moderate time or if i am totally abroad with my ansatz.
Re: Finding primes up to high numbers
There are more than 3*10^10 primes less than 10^12. Even ignoring how you generate them, how much memory do you need to store them all?
I'd say if you think you need all of those primes for any problem, you need to reevaluate your method.
I'd say if you think you need all of those primes for any problem, you need to reevaluate your method.
Re: Finding primes up to high numbers
The only efficient way to get the list of primes up to an specific number N is sieving.
The sieve of Aktin has a complexity of O(N) and also a Memory need of O(N).
So you can calculate:
A CPU has 23 *10^9 cycles per second.
Using the "PE maximum calculation time" of 1 minute (60s), it is possible to use ca. 1.5*10^11 cycles for the whole problem.
As N=10^12, your algorithm must check around 7 Numbers per cycle > impossible.
PS: The fastest solution needs a little bit more than 1 second.
The sieve of Aktin has a complexity of O(N) and also a Memory need of O(N).
So you can calculate:
A CPU has 23 *10^9 cycles per second.
Using the "PE maximum calculation time" of 1 minute (60s), it is possible to use ca. 1.5*10^11 cycles for the whole problem.
As N=10^12, your algorithm must check around 7 Numbers per cycle > impossible.
PS: The fastest solution needs a little bit more than 1 second.

 Posts: 3
 Joined: Sat May 16, 2015 3:43 pm
Re: Finding primes up to high numbers
Thank you very much for your fast answers.
I already assumed, that this method isnt the right solution.
The problem for me is, that i have an pure mathematic perspective on the problems which doesnt consider the calculation time and power. I have to rethink this one definitly. My i idea was, that, since i know how the prime factorization of the numbers have to look, i just count the possible combinations of the prime factors. But when it takes just one second, then there has to exist a completely different solution, with a different criterium.
I already assumed, that this method isnt the right solution.
The problem for me is, that i have an pure mathematic perspective on the problems which doesnt consider the calculation time and power. I have to rethink this one definitly. My i idea was, that, since i know how the prime factorization of the numbers have to look, i just count the possible combinations of the prime factors. But when it takes just one second, then there has to exist a completely different solution, with a different criterium.

 Posts: 3
 Joined: Sat May 16, 2015 3:43 pm
Re: Finding primes up to high numbers
Ok, i think maybe i am not ready for that one. Of Course the problem is clear, as I know the four types of numbers. But as i have no access to the primes, which build up all the numbers, because it needs to much calculations i can not use combination calculations to calculate the amount of numbers, the other way arround to just directly test the numbers is even slower than to test them for prime.
I also thought that i am maybe dont know some formula or function which can help me with that, like that the many function values are given an recursive solution, but actually cant believe that. I mean theres no analytical way to find primes, so there cant be an analytical way to find all those numbers.
I also wrote a program that gives me the number of these numbers for low n and i see that the number seem to increase nearly lineary.
I also thought that i am maybe dont know some formula or function which can help me with that, like that the many function values are given an recursive solution, but actually cant believe that. I mean theres no analytical way to find primes, so there cant be an analytical way to find all those numbers.
I also wrote a program that gives me the number of these numbers for low n and i see that the number seem to increase nearly lineary.

 Posts: 3
 Joined: Sat May 23, 2015 11:09 am
Re: Finding primes up to high numbers
I know that iterating all the primes up to 1e12/6 is too slow, but currently it's my only idea. It takes some 15 minutes, so I let it run... and got a result which is wrong, while for the three given values I get the right answers.
My results are
f(1e6) = 224427  surely right
f(1e7) = 2229293
f(1e8) = 21902470
f(1e9) = 214118140
f(1e10) = 2087650968
f(1e11) = 20330293700
f(1e12) = 197913151839  surely wrong
Could someone tell me where I started to err?
My results are
f(1e6) = 224427  surely right
f(1e7) = 2229293
f(1e8) = 21902470
f(1e9) = 214118140
f(1e10) = 2087650968
f(1e11) = 20330293700
f(1e12) = 197913151839  surely wrong
Could someone tell me where I started to err?

 Posts: 7
 Joined: Sun Dec 27, 2009 11:35 pm
Re: Finding primes up to high numbers
maaartinus wrote: f(1e7) = 2229293  wrong
f(1e8) = 21902470  correct
f(1e9) = 214118140  correct
f(1e10) = 2087650968  correct
f(1e11) = 20330293700  correct

 Posts: 3
 Joined: Sat May 23, 2015 11:09 am
Re: Finding primes up to high numbers
Thank you. I fixed f(1e7) to 2228418. Sadly, my f(1e12) didn't change and so all my values are right except for the only one I need. Damn, anything can be wrong, even my prime sieve as I hardly used it for such a big numbers before.
Did someone try bruteforcing the way I do? I'm partitioning the numbers into 3 groups (despite my solution being slow not saying more to avoid spoilers) and I could post the sizes of the groups to check.
Did someone try bruteforcing the way I do? I'm partitioning the numbers into 3 groups (despite my solution being slow not saying more to avoid spoilers) and I could post the sizes of the groups to check.

 Posts: 1
 Joined: Mon Aug 03, 2015 9:36 pm
Re: Finding primes up to high numbers
I brute forced a couple solutions requiring large primes. If you just need to iterate over all the primes
and not store them you can do it blockwise.
You only need to store the first sqrt(N) primes to check for primality for numbers up to N.
You should be able to go through all primes up to 1e12, but your solution will need some time.
and not store them you can do it blockwise.
You only need to store the first sqrt(N) primes to check for primality for numbers up to N.
You should be able to go through all primes up to 1e12, but your solution will need some time.