Prime pattern 6 +/- 1

[bplus]

Here is Prime Sieving with a 6 wheeler:

Code: (Select All)

' 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 = 100000000
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

PLUS: Once we have established primes, we can quickly factor numbers.