Posts: 2,693
Threads: 326
Joined: Apr 2022
Reputation:
217
05-16-2024, 08:13 AM
(This post was last modified: 05-16-2024, 11:53 AM by SMcNeill.)
A quick little method to get prime numbers from 2 to a little over 1,000,000.
Code: (Select All)
Screen _NewImage(1280, 900, 32)
_ScreenMove _Middle
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.
If IsPrime(i) Then Print i;
If i Mod 12000 = 0 Then Sleep: Cls
Next
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 "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
Restore prime_factors
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.
Read count
For i = 1 To count
Read factor
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_factors: 'for a list of prime factors for numbers from 1 to 1,000,000
Data 25: 'for numbers from 1 to 100
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 21: 'for numbers from 101 to 200
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 16
Data 211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293: 'up to 93,636 (306 ^ 2)
Data 16
Data 307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397: 'up to 160,000 (400 ^ 2)
Data 17
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 14
Data 503,509,521,523,541,547,557,563,569,571,577,587,593,599: 'up to 360,000 (600 ^ 2)
Data 16
Data 601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691: 'up to 490,000 (700 ^ 2)
Data 14
Data 701,709,719,727,733,739,743,751,757,761,769,773,787,797: 'up to 652,864 (808 ^ 2)
Data 15
Data 809,811,821,823,827,829,839,853,857,859,863,877,881,883,887: 'up to 820,836 (906 ^ 2)
Data 14
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 that this saves no tables, no values. Uses almost no memory. It's just direct elimination in the most efficient manner possible, for values from 2 to a little over 1,000,000. If someone wanted, they could continue this to go further, but it's all I need at the moment for my personal purposes, so I'll just post it as is and leave it for others to work on and enjoy if they ever want to.
Posts: 2,693
Threads: 326
Joined: Apr 2022
Reputation:
217
Updated what I had earlier with what I feel is a faster, easier-to-expand, and just all around friendler format. This will tell you almost instantly if any value less than 1,000,000 is a prime number or not. If anyone could use something like this for their own projects, feel free to make use of it however you want.
Posts: 54
Threads: 1
Joined: Apr 2022
Reputation:
7
05-16-2024, 01:01 PM
(This post was last modified: 06-05-2024, 09:11 AM by Sprezzo.)
-----
Posts: 2,693
Threads: 326
Joined: Apr 2022
Reputation:
217
(05-16-2024, 01:01 PM)Sprezzo Wrote: There are 78498 primes under 1 million and this program gets them all. Not bad.
Just curious: what are you using primes for? Hash table? Fraction simplification.
8 / 12 = 2 / 3
(I can quickly make a prime list to use for reducing those down quickly, or breaking them into denominators.)
Posts: 2,693
Threads: 326
Joined: Apr 2022
Reputation:
217
After some testing (which I personally found rather mind boggling), I've swapped over to a second version of this code which is even faster than what was above:
Code: (Select All)
Screen _NewImage(1280, 900, 32)
_Delay .5
_ScreenMove _Middle
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
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 "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
The difference here is that we use an array to store these values, and look them up from the array, rather than restore and read them as direct DATA statements.
For quite some time now, I was always under the impression that arrays had a good bit of overhead to them, and that raw DATA was optimized and READ faster than array access was from the compiler. Apparently that's not true, as array access is about 20 to 30 times faster than READ and DATA, from various tests I've been playing around with. That just completely turns my expectations upside down!!
And thus, Steve the Amazing adapts and adjusts!! If arrays are faster, so be it! I now have an version which does Prime Numbers up to a little over 1,000,000, via using arrays to store the data.
Posts: 649
Threads: 95
Joined: Apr 2022
Reputation:
22
05-16-2024, 11:26 PM
(This post was last modified: 05-16-2024, 11:29 PM by PhilOfPerth.)
(05-16-2024, 03:33 PM)SMcNeill Wrote: After some testing (which I personally found rather mind boggling), I've swapped over to a second version of this code which is even faster than what was above:
Code: (Select All)
Screen _NewImage(1280, 900, 32)
_Delay .5
_ScreenMove _Middle
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
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 "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
The difference here is that we use an array to store these values, and look them up from the array, rather than restore and read them as direct DATA statements.
For quite some time now, I was always under the impression that arrays had a good bit of overhead to them, and that raw DATA was optimized and READ faster than array access was from the compiler. Apparently that's not true, as array access is about 20 to 30 times faster than READ and DATA, from various tests I've been playing around with. That just completely turns my expectations upside down!!
And thus, Steve the Amazing adapts and adjusts!! If arrays are faster, so be it! I now have an version which does Prime Numbers up to a little over 1,000,000, via using arrays to store the data.
You've killed one of my dreams! For years now, I've been trying (just as an exercise) to find a "formula" that lists all primes, with no success.
Also had a go at finding PI, with the same result! Now I'll have to find another little conundrum to solve, to leave my mark in history!
Posts: 1,001
Threads: 50
Joined: May 2022
Reputation:
27
(05-16-2024, 08:13 AM)SMcNeill Wrote: A quick little method to get prime numbers from 2 to a little over 1,000,000.
Note that this saves no tables, no values. Uses almost no memory. It's just direct elimination in the most efficient manner possible, for values from 2 to a little over 1,000,000. If someone wanted, they could continue this to go further, but it's all I need at the moment for my personal purposes, so I'll just post it as is and leave it for others to work on and enjoy if they ever want to. I get an error message here, the _Orelse num is not recognized as a command word; remains white.
Posts: 1,001
Threads: 50
Joined: May 2022
Reputation:
27
I also wrote a program to determine prime numbers and tested it up to 1,000,000. Is the result fast, slow or acceptable?
Code: (Select All)
Option _Explicit
Dim As Long eingabe, anzahlprim, anzahl
Dim As Long primzahl, zahlenbereich
Dim As Single zeitstart, zeitende
Screen _NewImage(800, 600, 32)
anzahl = 0
Print Tab(15); "Ausgabe aller Primzahlen bis zur Eingabe"
Print
Input "Alle Primzahlen ausgeben bis: ", eingabe
Timer On
zeitstart = Timer
anzahlprim = 0
For primzahl = 2 To eingabe Step 1
zahlenbereich = 2
Do While primzahl Mod zahlenbereich <> 0
zahlenbereich = zahlenbereich + 1
Loop
If zahlenbereich = primzahl Then Print Using "#####"; primzahl;
If zahlenbereich = primzahl Then anzahlprim = anzahlprim + 1
Next
zeitende = Timer
Print: Print
Print Using "Sekunden: ####.##### "; zeitende - zeitstart
Print
Print Using "Bis ###,##### gibt es ##,#### Primzahlen"; eingabe, anzahlprim
End
Posts: 2,152
Threads: 222
Joined: Apr 2022
Reputation:
102
This is all a bunch of high school crap. I did all this stuff 50 years ago. I called it: Fast Primes at Ridgemont High
Pete
Posts: 1,001
Threads: 50
Joined: May 2022
Reputation:
27
(05-30-2024, 06:33 AM)Pete Wrote: This is all a bunch of high school crap. I did all this stuff 50 years ago. I called it: Fast Primes at Ridgemont High
Pete I knew it is well! Thanks, Pete!
|