Finding primes up to high numbers

[8FordPrefect8]

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 Miller-Rabin 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.

[DJohn]

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 re-evaluate your method.

[v6ph1]

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 2-3 *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.

[8FordPrefect8]

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.

[8FordPrefect8]

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.

[maaartinus]

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?

[mirzauzairbaig]

f(1e7) = 2229293 - wrong
f(1e8) = 21902470 - correct
f(1e9) = 214118140 - correct
f(1e10) = 2087650968 - correct
f(1e11) = 20330293700 - correct

[maaartinus]

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.

[michaelcode]

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 block-wise.
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.