View Single Post
2010-10-02, 19:26   #10
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT)

22×1,423 Posts

Quote:
 Originally Posted by Ken_g6 Having looked into the math, I'm convinced that Max is correct. (Though he may have gotten that figure from me.) Although going from one to two k's in sr2sieve doesn't double the runtime, going from two to three should increase the runtime as much as going from one to two did. Or maybe I'm wrong and Geoff found a better way?
Well with testing sr2sieve seems to be sqrt(k_count)
I sieved ks(1,3,5 etc excluding squares because of algebraics) to 1e8 with srsieve and then sieved a range of 2e8 starting from 1e12. A spreadsheet gave me a regression line with formula 23.76*k_count^0.51 which is very close to 1/2 which is sqrt(k_count).
Code:
k_count      seconds
1              27
4              42
9              67
12             80
16             94
18             101
20             118
24             129
30             148

Last fiddled with by henryzz on 2010-10-02 at 19:27