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


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: 6 Guest(s)