6 Wheel Sieve 78498 primes from first million integers in .046 secs
Code: (Select All)
_Title "6 Wheel Sieve"
' 6 wheel sieve.bas for QB64 fork (B+=MGA) 2017-08-30 copy and trans to QB64
'translated from: First Factors.bas for SmallBASIC 11/27/14 (bpf.org post)
'topN = 1000000, primes 78,498, .17 secs, 8169 twins last 999959, 999961
'topN = 10000000, primes 664,579, 1.85 secs, 58,980 twins last 9999971, 9999973
'topN = 100000000, primes 5,761,455, 20.69 secs, 440,312 twins last 99999587, 99999589
' out of memory for 1 billion
'compare to 30 wheel
'topN = 1000000, primes 78,498, .15 secs, 8169 twins last 999959, 999961
'topN = 10000000, primes 664,579, 1.81 secs, 58,980 twins last 9999971, 9999973
'topN = 100000000, primes 5,761,455, 19.65 secs, 440,312 twins last 99999587, 99999589
' out of memory for 1 billion
'compare to 2310 wheel sieve WOW the 30 wheel is faster!
'QB64 results from 2310 wheel
'topN = 1000000, primes 78,498, .18 secs, 8169 twins last 999959, 999961
'topN = 10000000, primes 664,579, 1.98 secs, 58,980 twins last 9999971, 9999973
'topN = 100000000, primes 5,761,455, 21.57 secs, 440,312 twins last 99999587, 99999589
' out of memory for 1 billion
_Define A-Z As _INTEGER64
Option Base 1
Common Shared ff(), topN
topN = 1223 'first 200 primes test
topN = 1000000
testlimitN = Sqr(topN)
'First Factors array is 0 for prime number or contains the numbers lowest factor
Dim ff(topN + 6)
tStart# = Timer(.001)
For i = 0 To topN Step 6
ff(i + 2) = 2: ff(i + 3) = 3: ff(i + 4) = 2: ff(i + 6) = 2
Next
ff(2) = 0: ff(3) = 0 'fix first 2 factors
For pcand = 5 To testlimitN Step 2
If ff(pcand) = 0 Then
For i = pcand * pcand To topN Step 2 * pcand
If ff(i) = 0 Then ff(i) = pcand
Next
End If
Next
'count primes
For i = 2 To topN
If ff(i) = 0 Then p = p + 1
Next
tStop# = Timer(.001)
tTime# = tStop# - tStart#
Print "For "; topN; " numbers there are "; p; " primes in "; tTime#; " secs."
If 0 Then ' <<<<< uncomment this as needed
'file twin primes data
Open "Twin primes.txt" For Output As #1
lastp = -1
For i = 2 To topN
If ff(i) = 0 Then
If i - lastp = 2 Then
Print #1, Str$(lastp) + ", " + Str$(i) + " Middle/6 = " + Str$((i - 1) / 6) + ": " + factors$((i - 1) / 6)
tCount = tCount + 1
End If
lastp = i
End If
Next
Close #1
Print "Found "; tCount; " Twin Primes in first "; topN; " integers."
End If ' <<<<<<<<<<<<< uncomment this as needed
'test some factoring of numbers
factorMe = 10
While factorMe > 1
Input "Enter a number to factor, 0 quits "; factorMe
If factorMe < 2 Then Exit While Else Print factors$(factorMe)
Wend
Function factors$ (n)
If n > topN Then factors$ = "Error: too high a number.": Exit Function
f$ = ""
While ff(n) <> 0
f$ = f$ + Str$(ff(n)) + " "
n = n / ff(n)
Wend
factors$ = f$ + Str$(n)
End Function
b = b + ...