Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Fast Primes
#19
I kept this prime number generator around for some time for instances concerning yet another prime number program:

It first uses the sieve to create the first 1024 primes into an array then uses that array to use a second sieve generator.

Fast it calculates the primes up to 1M in less than a second and 10M in 15 seconds. On a 64-bit AMD Hexacore at 3.90 Ghz

Also prompts to print or count primes. And prompts for upper limit for prime number. Displays runtime.

Code: (Select All)
Rem The Prime Number Generator v2.0a PD 2024.
Rem   First release (06/06/2024)
Rem   Release v2.0a (06/10/2024)
Rem     Adds IsPrime to check test value.
DECLARE FUNCTION Keyboard$ ()
DECLARE FUNCTION FormatString$ (s#)
DECLARE SUB Dot.Display (VarA#, VarB#, VarC!)
DECLARE SUB Back.Space ()
Rem $Dynamic
DefDbl A-Z
On Error GoTo Error.Routine
On Timer(1) GoSub StatusLine
Timer On
Rem _Title "Prime Generstor"
Rem _ScreenMove _Middle
GoSub StatusLine
StartLoop:
Width 80, 25
Cls
Color 14
Print "Prime number generator v2.0a."
Color 15
Do
   Print "Enter (T)est/(P)rint/(C)ount?";
   Do
      A$ = InKey$
      If Len(A$) Then Exit Do
   Loop
   A$ = UCase$(A$)
   If A$ = "T" Then
      Print: PrintPrimes = -2
      Do
         Print "Enter test prime?";
         T$ = Keyboard$
         If CDbl(Val(T$)) < 32768 Then
            T = CInt(Val(T$))
         Else
            T = CDbl(Val(T$))
         End If
         Select Case T
            Case Is < 0, 0, 1 ' anything less than 2 is not a prime.
               Print T; "is not prime."
            Case 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 ' short list of first 12 primes.
               Print T; "is prime."
            Case Else
               S = 1024
               Exit Do
         End Select
      Loop
      Exit Do
   End If
   If A$ = "P" Then Print: PrintPrimes = -1: Exit Do
   If A$ = "C" Then Print: PrintPrimes = 0: Exit Do
   Print
Loop
Do
   Print "Enter fast display(Y/N)?";
   Do
      A$ = InKey$
      If Len(A$) Then Exit Do
   Loop
   A$ = UCase$(A$)
   If A$ = "Y" Then Print: FastDisplay = -1: Exit Do
   If A$ = "N" Then Print: FastDisplay = 0: Exit Do
   Print
Loop
If PrintPrimes = -2 Then GoTo ContinueLoop
Do
   Print "Upper prime limit(10-1000000)?";
   U$ = Keyboard$
   If CDbl(Val(U$)) < 32768 Then
      U = CInt(Val(U$))
   Else
      U = CDbl(Val(U$))
   End If
   If U = 0 Then U = 1000000: Exit Do
   If U >= 10 Then Exit Do
Loop
ContinueLoop:
Do
   Print "Upper sieve limit(1024-32767)?";
   S$ = Keyboard$
   If CDbl(Val(S$)) < 32768 Then
      S = CInt(Val(S$))
   Else
      S = CDbl(Val(S$))
   End If
   If S = 0 Then S = 1024: Exit Do
   If S >= 1024 Then Exit Do
Loop
ReDim p(S) As Double
T! = Timer
Color 14
Print "Storing sieve array of "; FormatString$(S); " elements."
VarD = 0
VarE = 0
VarF! = Timer
StartTimer! = Timer
q = 0
Z = 1
Do
   If FastDisplay = 0 Then
      Elapsed! = Timer - StartTimer!
      If Elapsed! < 0! Then Elapsed! = Elapsed! + 86400!
      If Elapsed! >= 1! Then
         Call Dot.Display(VarD, VarE, VarF!)
         StartTimer! = Timer
      End If
   End If
   Z = Z + 1
   F = 0
   For l = 2 To Int(Sqr(Z))
      If Z / l = Int(Z / l) Then
         F = -1
         Exit For
      End If
   Next
   If F = 0 Then
      q = q + 1
      p(q) = Z
   End If
   If q = S Then
      Exit Do
   End If
Loop
Do
   If Pos(0) > 1 Then
      Locate CsrLin, Pos(0) - 1, 0
      Print " ";
      Locate CsrLin, Pos(0) - 1, 1
   Else
      Exit Do
   End If
Loop
' display calculated runtime.
Z! = Timer - T!
If Z! < 0! Then Z! = Z! + 86400!
If Z! > 0! Then
   Z$ = Str$(Z!)
   If InStr(Z$, ".") Then Z$ = Left$(Z$, InStr(Z$, ".") + 1)
   Print " Runtime:"; Z$; " seconds."
End If
Print "Calculating primes.."
Print "Maximum prime: ";
x# = (p(S) * p(S))
Print FormatString$(x#)
Color 15
Print "Press <escape> to quit:"
If PrintPrimes = -2 Then
   ' check sieve arrays.
   Z = T
   GoSub IsPrime
   Select Case F
      Case 0
         Print "Value "; FormatString$(T); " is prime."
      Case -1
         Print "Value "; FormatString$(T); " is not prime."
      Case -2
         Print "Array limit exceeded."
   End Select
   GoTo EndLoop
End If
If PrintPrimes Then
   Print 2 ' first prime is always 2.
End If
VarD = 0
VarE = 0
VarF! = Timer
StartTimer! = Timer
c = 0
Z = 1
x = 0
Do
   Z = Z + 2
   q = 0
   F = 0
   Do
      If FastDisplay = 0 Then
         Elapsed! = Timer - StartTimer!
         If Elapsed! < 0! Then Elapsed! = Elapsed! + 86400!
         If Elapsed! >= 1! Then
            Call Dot.Display(VarD, VarE, VarF!)
            StartTimer! = Timer
         End If
      End If
      q = q + 1
      If q > S Then
         Exit Do
      End If
      If p(q) > Int(Sqr(Z)) Then
         Exit Do
      End If
      If Z / p(q) = Int(Z / p(q)) Then
         F = -1
         Exit Do
      End If
   Loop
   If q > S Then
      Exit Do
   End If
   If F = 0 Then
      c = c + 1
      If PrintPrimes Then
         Print Z
      End If
      If InKey$ = Chr$(27) Then
         Exit Do
      End If
      If Z > U Then
         Exit Do
      End If
      If Z > (p(S) * p(S)) Then
         Exit Do
      End If
   End If
Loop

' clear dots.
Do
   If Pos(0) > 1 Then
      Locate CsrLin, Pos(0) - 1, 0
      Print " ";
      Locate CsrLin, Pos(0) - 1, 1
   Else
      Exit Do
   End If
Loop

' display totals.
Print "Last prime: ";
Print FormatString$(Z)
Print "Primes: ";
Print FormatString$(c + 1)

' display calculated runtime.
Z! = Timer - T!
If Z! < 0! Then Z! = Z! + 86400!
Z$ = Str$(Z!)
If InStr(Z$, ".") Then Z$ = Left$(Z$, InStr(Z$, ".") + 1)
Print " Runtime:"; Z$; " seconds."

' prompt to run again.
EndLoop:
Do
   Color 15
   Print "Run again(Y/N)";
   Do
      A$ = InKey$
      If Len(A$) Then Exit Do
   Loop
   A$ = UCase$(A$)
   If A$ = "Y" Then GoTo StartLoop
   If A$ = "N" Then Exit Do
   Print
Loop
GoSub ClearLine
Color 7
End

' standard error trap
Error.Routine:
Color 12
Print "Error"; Err;
If Err = 6 Then Print " Overflow";
Print
Color 7
Resume EndLoop
End

' display statusline in timer loop.
StatusLine:
X1 = CsrLin
Y1 = Pos(0)
Locate 25, 1
Print "Prime generator " + Date$ + " " + Time$;
If q > 0 Then
   Print " Test:"; q; "     ";
Else
   Print Space$(15);
End If
Locate X1, Y1
Return

' clear statusline in timer loop.
ClearLine:
X1 = CsrLin
Y1 = Pos(0)
Locate 25, 1
Print Space$(79);
Locate X1, Y1
Return

' see if Z is prime. returns F as false if prime.
IsPrime:
q = 0
F = 0
' check in sieve array first.
For x = 1 To S
   If Z = p(x) Then Return
Next
' calculate prime next.
Do
   If FastDisplay = 0 Then
      elapsed = Timer - starttimer
      If elapsed < 0 Then elapsed = elapsed + 86400
      If elapsed >= 1 Then
         Call Dot.Display(VarD, VarE, VarF!)
         starttimer = Timer
      End If
   End If
   q = q + 1
   If q > S Then
      F = -2
      Exit Do
   End If
   If p(q) > Int(Sqr(Z)) Then
      Exit Do
   End If
   If Z / p(q) = Int(Z / p(q)) Then
      F = -1
      Exit Do
   End If
Loop
' clear dots.
Do
   If Pos(0) > 1 Then
      Locate CsrLin, Pos(0) - 1, 0
      Print " ";
      Locate CsrLin, Pos(0) - 1, 1
   Else
      Exit Do
   End If
Loop
Return

Sub Back.Space
   If Pos(0) > 1 Then
      Locate CsrLin, Pos(0) - 1, 0
      Print " ";
      Locate CsrLin, Pos(0) - 1, 1
   End If
End Sub

Sub Dot.Display (VarA, VarB, VarC!)
   VarG! = Timer - VarC!
   If VarG! < 0! Then VarG! = VarG! + 86400!
   If VarG! >= 1! Then
      VarC! = Timer
      If VarA = 0 Then
         VarB = VarB + 1
         Print ".";
         If VarB = 5 Then
            VarA = -1
            VarB = 0
         End If
      Else
         VarB = VarB + 1
         Call Back.Space
         Print " ";
         Call Back.Space
         If VarB = 5 Then
            VarA = 0
            VarB = 0
         End If
      End If
   End If
End Sub

' formats a numeric string.
Function FormatString$ (s)
   x$ = ""
   s$ = Str$(s)
   s$ = LTrim$(s$)
   If InStr(s$, ".") Then s$ = Left$(s$, InStr(s$, ".") - 1)
   For l = Len(s$) To 3 Step -3
      x$ = Mid$(s$, l - 2, 3) + "," + x$
   Next
   If l > 0 Then
      x$ = Mid$(s$, 1, l) + "," + x$
   End If
   If Len(s$) < 3 Then
      x$ = s$
   End If
   If Right$(x$, 1) = "," Then
      x$ = Left$(x$, Len(x$) - 1)
   End If
   FormatString$ = x$
End Function

' get inkey during timer loop.
Function Keyboard$
   V$ = ""
   Do
      A$ = ""
      Do
         A$ = InKey$
         If Len(A$) Then Exit Do
      Loop
      If A$ >= "0" And A$ <= "9" Then
         V$ = V$ + A$
         Print A$;
      End If
      If A$ = Chr$(8) Then '  backspace
         If Len(V$) Then
            V$ = Left$(V$, Len(V$) - 1)
            X1 = CsrLin
            Y1 = Pos(0)
            Locate X1, Y1 - 1
            Print " ";
            Locate X1, Y1 - 1
         End If
      End If
      If A$ = Chr$(27) Then
         For V = 1 To Len(V$)
            X1 = CsrLin
            Y1 = Pos(0)
            Locate X1, Y1 - 1
            Print " ";
            Locate X1, Y1 - 1
         Next
         V$ = ""
      End If
      If A$ = Chr$(13) Then Exit Do
   Loop
   Keyboard$ = V$
   Print
End Function

An example of a small prime generator:

Code: (Select All)

Rem small prime number sieve.
DefLng A-Z
Rem $Dynamic
Dim p(1024) As Integer
For x = 2 To 1024
  For l = x + x To 1024 Step x
      If l <= 1024 Then
        p(l) = -1
      End If
  Next
Next
For l = 2 To 1024
  If p(l) = 0 Then Print l;
Next
End



Attached Files
.zip   PRIME2.ZIP (Size: 4.54 KB / Downloads: 24)
Reply


Messages In This Thread
Fast Primes - by SMcNeill - 05-16-2024, 08:13 AM
RE: Fast Primes - by SMcNeill - 05-16-2024, 11:56 AM
RE: Fast Primes - by Sprezzo - 05-16-2024, 01:01 PM
RE: Fast Primes - by SMcNeill - 05-16-2024, 01:32 PM
RE: Fast Primes - by SMcNeill - 05-16-2024, 03:33 PM
RE: Fast Primes - by PhilOfPerth - 05-16-2024, 11:26 PM
RE: Fast Primes - by Kernelpanic - 05-29-2024, 05:53 PM
RE: Fast Primes - by Kernelpanic - 05-29-2024, 06:03 PM
RE: Fast Primes - by SMcNeill - 05-30-2024, 12:03 PM
RE: Fast Primes - by Pete - 05-30-2024, 06:33 AM
RE: Fast Primes - by Kernelpanic - 05-30-2024, 11:51 AM
RE: Fast Primes - by Kernelpanic - 05-30-2024, 12:11 PM
RE: Fast Primes - by SMcNeill - 05-30-2024, 12:21 PM
RE: Fast Primes - by Kernelpanic - 05-30-2024, 12:55 PM
RE: Fast Primes - by SMcNeill - 05-31-2024, 03:55 AM
RE: Fast Primes - by Kernelpanic - 06-03-2024, 08:58 PM
RE: Fast Primes - by SMcNeill - 06-03-2024, 10:45 PM
RE: Fast Primes - by Kernelpanic - 06-03-2024, 11:38 PM
RE: Fast Primes - by eoredson - 06-06-2024, 04:44 AM



Users browsing this thread: 14 Guest(s)