06-08-2022, 02:49 PM
@JRACE
This was a nice catch on Danilin's code:
If j >= p ^ 0.5 Then f = 2 'original line moved outside inner loop
But as far as speed goes, sieving is way faster than testing so many times for divisibility with MOD. But you need an array to save results. Maybe the RC challenge was looking to do it without arrays? BUT who really needs to know the 10001th dang prime number? or any nth prime number. Most applications use primes info for factoring so you need to collect prime info in an array for vast range of factors and sieving is fastest for that to do something more practical than this RC challenge.
Sieving with wheels is even faster! The example I showed was sieving with a wheel of 6 the samllest, which takes out all multiples of 2 and 3 for prime candidates even before you start sieving. That's 1/2 of all numbers plus 1/3 of 1/2 = 1/6 of the remaining prime candidates.
Sieving with a 210 wheel; takes out 2, 3, 5, 7 multiples (2*3*5*7 = 210) before sieving with remaining prime candidates another speed improvement. The wheel size eventually get unwieldy but it depends on the number of integers your prime info (what I call array or first factors) needs to cover.
This was a nice catch on Danilin's code:
If j >= p ^ 0.5 Then f = 2 'original line moved outside inner loop
But as far as speed goes, sieving is way faster than testing so many times for divisibility with MOD. But you need an array to save results. Maybe the RC challenge was looking to do it without arrays? BUT who really needs to know the 10001th dang prime number? or any nth prime number. Most applications use primes info for factoring so you need to collect prime info in an array for vast range of factors and sieving is fastest for that to do something more practical than this RC challenge.
Sieving with wheels is even faster! The example I showed was sieving with a wheel of 6 the samllest, which takes out all multiples of 2 and 3 for prime candidates even before you start sieving. That's 1/2 of all numbers plus 1/3 of 1/2 = 1/6 of the remaining prime candidates.
Sieving with a 210 wheel; takes out 2, 3, 5, 7 multiples (2*3*5*7 = 210) before sieving with remaining prime candidates another speed improvement. The wheel size eventually get unwieldy but it depends on the number of integers your prime info (what I call array or first factors) needs to cover.
b = b + ...