Put up a new version (it'll get moderator-approved sometime monday). Still same the brute-force method, but hard-coded checks up to the first full data page of the table of numbers (622 for mine; put up to 625 in code) and limited the factor division tests to 627 to the square root of the candidate prime. This sped it up by 40% to one million . Primes from 1 to 250K might be slower. A smaller change eliminated the sort for the ROW_NUMBER (for nth prime queries), but it had only a .1 second impact.
The speed of this is solely because it is 100% set-based, and now limits data-access on the table of numbers (eliminating it for 84%, removing 1 logical I/O for the rest), not because of any fancy algorithm. Coding in C++ with the fancy algorithms and using SQLBulkCopy to insert the data would still be the fastest way.
1-to-1,000,000
Table 'Primes'. Scan count 0, logical reads 158311, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Counter'. Scan count 81940, logical reads 328566, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 10172 ms, elapsed time = 10283 ms.
(78498 row(s) affected)
Table 'Primes'. Scan count 1, logical reads 265, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 156 ms, elapsed time = 153 ms.
SQL Server Execution Times:
CPU time = 156 ms, elapsed time = 158 ms.
Table 'Primes'. Scan count 1, logical reads 225, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 140 ms, elapsed time = 140 ms.
SQL Server Execution Times:
CPU time = 140 ms, elapsed time = 151 ms.
Table 'Primes'. Scan count 1, logical reads 795074, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 1, logical reads 158276, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 1843 ms, elapsed time = 1857 ms.
(78498 row(s) affected)
SQL Server Execution Times:
CPU time = 12656 ms, elapsed time = 12808 ms.
1-to-772,524 (table of numbers that fits a 2-level clustered index snugly, doubled by the *2+1)
Table 'Primes'. Scan count 0, logical reads 124884, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Counter'. Scan count 63469, logical reads 191027, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 7156 ms, elapsed time = 7292 ms.
(61922 row(s) affected)
Table 'Primes'. Scan count 1, logical reads 210, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 125 ms, elapsed time = 117 ms.
SQL Server Execution Times:
CPU time = 125 ms, elapsed time = 124 ms.
Table 'Primes'. Scan count 1, logical reads 177, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 94 ms, elapsed time = 115 ms.
SQL Server Execution Times:
CPU time = 94 ms, elapsed time = 118 ms.
Table 'Primes'. Scan count 1, logical reads 627187, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
Table 'Worktable'. Scan count 1, logical reads 124854, physical reads 0, read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.
SQL Server Execution Times:
CPU time = 1437 ms, elapsed time = 1435 ms.
(61922 row(s) affected)
SQL Server Execution Times:
CPU time = 9187 ms, elapsed time = 9395 ms.