Re: Fast prime generators
- Hello Mark,
i wrote a prime sieve with Cuda on a Gpu Geforce 450 with 192 cores.
All work is done on the Gpu.
I get as result only the numbers of primes in arithmetic progressions.
The Programm needs approximately 1 month for counting all primes below 10^15
I am not sure if this is a good result, but i could give you the code,
if you want, it is quite nice and uses not the sieve of Eratosthenes,
but more a sieve of Ulam in some derivated form.
Does it make any sense to calculate the numbers of primes in arithmetic progressions up to 10^15 ?
Nice greetings from the primes
I had a methodology(may be not efficient had a intuition it will be useful) to generate all odd composite. Factors of all odd composites are predetermined through multiples of 4. Let A(n) = 4n where n = 1,2,3... Then A(n) = P1Q1 = P2Q2 = ..... = PkQk be the 'K' possible set of distinct even factors(means both Pk,Qk should even) such that Pk > Pk-1 > Pk-2 > ....> P1 then (Pk + 1) (Qk + 1), (Pk-1 + 1)(Qk-1 + 1), ...... (P1 + 1)(Q 1 + 1) will eventually generate all odd composite numbers. For e.g. A(1) = 4 = 2x2 here P1 = 2, Q1 = 2. Then (P1 + 1)(Q 1 + 1) = (2 + 1)(2 +1) = 9 First odd composite. A(2) = 8 = 2x4 here P1 = 2, Q1 = 4. Then (P1 + 1)(Q 1 + 1) = (2 + 1)(4 +1) = 15 second odd composite A(3) = 12 = 2x6 => 3x7 = 21 third odd composite A(4) = 16 = 2x8 = 4x4 => 5x5 =25 fourth odd composite and 3x9 = 27 fifth odd composite like that it continues. Based on this i found a methodology to
sieve Primes in given range 'a' to 'b' a,b both odd numbers. Write all the odd composite between 'a' to 'b' Find 'm' even such that 3(m + 1) <= 'a' < 3(u + 3) Now v= u/2 Calculate 4v = P1Q1 = P2Q2 = ..... = PkQk Then omit the following numbers (Pk + 1) (Q k + 1), (Pk-1 + 1)(Q k-1 + 1), ...... (P1 + 1)(Q 1 + 1) which falls in the range 'a' to 'b' Now increment 'k' and repeat the procedure till (Pk + 1) (Q k + 1) > b. Now the remaining numbers are prime.
[Non-text portions of this message have been removed]