Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Fast Primes
#11
(05-29-2024, 06:03 PM)Kernelpanic Wrote: I also wrote a program to determine prime numbers and tested it up to 1,000,000. Is the result fast, slow or acceptable?

[Image: Primzahlen2024-05-29.jpg]

About 3 minutes for your code. About 5 seconds for what I've got. You decide for yourself if it's fast, slow, or acceptable. Smile

Code: (Select All)
Screen _NewImage(1280, 900, 32)
_Delay .5
_ScreenMove _Middle
t# = Timer
For i = 1 To 999999 'I didn't stop at 1,000,000 just cause I didn't want that last SLEEP/CLS to erase the last page. Big Grin
If IsPrime(i) Then Print i;
' If i Mod 10000 = 0 Then Sleep: Cls
Next
t1# = Timer
'Beep 'an audible warning so folks can take their finger off whatever key they're using to spam past the SLEEP statements.
'_Delay 2 'and time for them to let go of that key
'_KeyClear 'so if they're using ENTER as the "Get on with it damn ya!" key, it won't blow past the manual test.
Print
Print
Print Using "###.#### seconds to get AND PRINT primes from 1 to 1,000,000."; t1# - t#
Print




Print "Feel free to do some independent tesing to see if my response is speedy enough for you:"
Do
Input "Give me a number from 0 to 1,016,064 and I'll tell you if it's prime or not. (Zero quits.) =>"; num
If IsPrime(num) Then
Print num; "is, indeed, a prime number!"
Else
Print "Nope!"; num; "is not prime!"
End If
Loop Until num = 0
System


Function IsPrime (num)
'to check for any given number less than 1,016,064, we only have to do a maximum of 170 comparisons
'as the max value we ever have to check against is the SQR of our number.
'for example, no value higher than 10 could ever be a factor in 100 and be prime!
'so for numbers less than 1,000,000, all we need do is compare them against factors less than 1,000.
'and there's not that many of them, as you can see below!
If num < 2 _Orelse num > 1016064 Then Exit Function
Static As Long Prime_Array_Init, Prime_Factors(1 To 168), Factor_Count(1 To 10)
Dim As Long factor_on, i, j, factor
If Prime_Array_Init = 0 Then
Prime_Array_Init = -1
Restore Prime_Factor_Count
For i = 1 To 10: Read Factor_Count(i): Next
For i = 1 To 168: Read Prime_Factors(i): Next
End If

IsPrime = -1
For j = 1 To 10 'broken down to give 10 quick exit points so we don't check every value for an answer.
For i = 1 To Factor_Count(j)
factor_on = factor_on + 1
factor = Prime_Factors(factor_on)
If num <= factor Then
Exit Function
Else
If num Mod factor = 0 Then IsPrime = 0: Exit Function
End If
Next
If num < factor * factor Then Exit Function
Next

Exit Function
Prime_Factor_Count: 'each value here represents the number of prime factors in number increments of 100
'for example, there are 25 prime numbers between 1 and 100, 21 primes between 101 and 200, ect...
Data 25,21,16,16,17,14,16,14,15,14
'and the actual prime factors go below here
Data 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97: 'factors up to 10,000 (100 ^ 2)
Data 101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199: 'up to 44,100 (210 ^ 2)
Data 211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293: 'up to 93,636 (306 ^ 2)
Data 307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397: 'up to 160,000 (400 ^ 2)
Data 401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499: 'up to 252,004 (502 ^ 2)
Data 503,509,521,523,541,547,557,563,569,571,577,587,593,599: 'up to 360,000 (600 ^ 2)
Data 601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691: 'up to 490,000 (700 ^ 2)
Data 701,709,719,727,733,739,743,751,757,761,769,773,787,797: 'up to 652,864 (808 ^ 2)
Data 809,811,821,823,827,829,839,853,857,859,863,877,881,883,887: 'up to 820,836 (906 ^ 2)
Data 907,911,919,929,937,941,947,953,967,971,977,983,991,997: 'up to 1,01,064 (1008 ^ 2)
End Function

Note -- it takes just fractions of a second to calculate the primes. The vast majority of time here is spend on PRINT statements. Smile
Reply
#12
Quote:Note -- it takes just fractions of a second to calculate the primes. The vast majority of time here is spend on PRINT statements. 
I couldn't run your program because of the error. I know that my program isn't particularly fast, but it's probably the easiest way to determine prime numbers.
I think I found that in the math dictionary.
Reply
#13
(05-30-2024, 12:11 PM)Kernelpanic Wrote:
Quote:Note -- it takes just fractions of a second to calculate the primes. The vast majority of time here is spend on PRINT statements. 
I couldn't run your program because of the error. I know that my program isn't particularly fast, but it's probably the easiest way to determine prime numbers.
I think I found that in the math dictionary.

The _OrElse isn't an error.  It's just a case of you needing to upgrade your version of QB64PE.  Smile
Reply
#14
Quote:The _OrElse isn't an error.  It's just a case of you needing to upgrade your version of QB64PE.
No, can't be! I have the latest version (I always use the latest version):

[Image: QB64-neuste2024-05-30.jpg]
Reply
#15
(05-30-2024, 12:55 PM)Kernelpanic Wrote:
Quote:The _OrElse isn't an error.  It's just a case of you needing to upgrade your version of QB64PE.
No, can't be! I have the latest version (I always use the latest version):

[Image: QB64-neuste2024-05-30.jpg]

I'd suggest trying another download and extract to a fresh directory.  13.1 definitely has _OrElse in it, and it should definitely NOT be white for you.  (It should be the same color as all the rest of your keywords.)

If a fresh download doesn't fix the glitch, then we'll want to know what OS/version you downloaded and are using, and we'll need to look into what the heck is going on.  The simple fact that nobody else has mentioned it not working, however, leads me to believe that your version is corrupted, or out of date, or pathing wrong, or some other add issue.
Reply
#16
Quote:I'd suggest trying another download and extract to a fresh directory.  13.1 definitely has _OrElse in it, and it should definitely NOT be white for you.  (It should be the same color as all the rest of your keywords.)

If a fresh download doesn't fix the glitch, then we'll want to know what OS/version you downloaded and are using, and we'll need to look into what the heck is going on.  The simple fact that nobody else has mentioned it not working, however, leads me to believe that your version is corrupted, or out of date, or pathing wrong, or some other add issue.
Sorry, I only saw it now. - The example from the wiki works (it can't be the download version):

Code: (Select All)

Print "Trying _ORELSE"

' _ORELSE performs short-circuiting logical conjunction and hence for "strawberry", only isFruit() is called
If isFruit("strawberry") _Orelse isRed("strawberry") _Orelse isSeasonal("strawberry") Then
  Print "Probably a strawberry."
Else
  Print "Certainly not a strawberry."
End If

Print
Print "Trying OR"

' OR does not performs short-circuiting logical conjunction and hence all is***() functions are called
If isFruit("strawberry") Or isRed("strawberry") Or isSeasonal("strawberry") Then
  Print "Probably a strawberry."
Else
  Print "Certainly not a strawberry."
End If

End

Function isFruit%% (fruit As String)
  Print "isFruit() called!"
  isFruit = (fruit = "strawberry")
End Function

Function isRed%% (fruit As String)
  Print "isRed() called!"
  isRed = (fruit = "strawberry")
End Function

Function isSeasonal%% (fruit As String)
  Print "isSeasonal() called!"
  isSeasonal = (fruit = "strawberry")
End Function

[Image: Or-Else-Problem2024-06-03-224850.jpg]

Your version with _OrElse still shows an error.
[Image: Or-Else-Problem-2-2024-06-03.jpg]

My system: Windows 10 Prof, latest updates.
Reply
#17
I honestly don't know what else to tell you.  As you can see, _ORELSE is a keyword for the language.  Why it's bugging out on that one line is beyond me.

All I can suggest is to change _ORELSE to a simple OR and then see how that line performs.  If it's still glitchy after that...  I'm all out of ideas!  Wink
Reply
#18
I just copied the source code again and now it works . . .  Huh  Now _OrElse was immediately recognizable as a command word.

I'll file this under: Mysterious cases in programming!  Dodgy

[Image: Ot-Else-OK-2024-06-04-013247.jpg]
Reply
#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




Users browsing this thread: 1 Guest(s)