I just did a forum search and found zero references to this topic. It is an otherwise very well covered subject that I've personally never had much interest in. Almost everybody has heard of it and almost no one knows what its good for. I'm talking about prime numbers.
For puzzler #14 we wonder how best to generate a list of the first 10,000 prime numbers. By generate I mean create the list using a Macro Scheduler script that performs mathematical wizardry rather than a script that pulls the data from one of the (literally) one Billion web pages that Google finds if you search for "prime number list".
I have a script that takes about 20 minutes to generate the list. For reference the first prime number is "2" and according to my calculations, the ten thousandth prime number is "104,729". I'm using the brute force method I was taught in Junior High School roughly 57 years ago. Oddly, for something I've never used I recalled the method well enough to create an accurate list.
For general interest, the largest prime number has 24,862,048 digits. Lets not calculate that one.
Another point of general interest, this is the first puzzler in 7 years that has a real answer. We hope it has more than one answer. Unfortunately it will be the 6th puzzler for which I have no points to bestow upon the winner. Only my genuine respect and admiration. The winner, assuming there will be entrants, will be selected by our panel of judge from the scripts provided by said entrants.
If there are no worthy entries by the end of this month, The panel of judge will declare me to be the winner and I will post my magnificent winning script. Nobody wants that to happen.
The Unofficial Macro Scheduler Puzzler #14
Moderators: Dorian (MJT support), JRL
Re: The Unofficial Macro Scheduler Puzzler #14
Hi, here is my attempt... On my machine it runs in around 6-7 min. Let's see if it matches your numbers and then interesting to see what other people come up with. The SRT at the end is just there to join the array elements into a string.
Code: Select all
Timer>start
Let>max=104729
Let>ctPrimes=0
ArrayDim>Primes,ctPrimes
Let>i=1
While>i<=max
Add>i,1
Assigned>Sieve_%i%,isSieveAssigned
If>isSieveAssigned=FALSE
Add>ctPrimes,1
ArrayDim>Primes,ctPrimes
Let>Primes_%ctPrimes%=i
Let>j={%i%*2 - %i%}
While>j<=max
Add>j,i
Let>Sieve_%j%=TRUE
EndWhile
EndIf
EndWhile
// Join array elements in "Primes" to string "resPrimes"
GoSub>Join,"Primes",%CRLF%,0,"resPrimes"
Timer>end
Let>time={(%end%-%start%)/60000}
Let>time={(Round(%time%*100)/100)}
MDL>Time: %time% min%CRLF%=====%CRLF%%resPrimes%
//SRT Join,"Array Name",delimiter,ending delimiter 0/1,"Result Variable Name"
SRT>Join
//Get the Array name w/o "" into Join_Arr_1
RegEx>(?<=^").+(?="$),%Join_Var_1%,0,Join_Arr,Join_N,0
ArrayCount>Join_Arr_1,Join_Arr_Count
Let>Join_delimiter=%Join_Var_2%
Let>Join_Res=
Let>Join_ct=0
While>Join_ct<Join_Arr_Count
Let>Join_ct=%Join_ct%+1
Let>Join_tmp=%Join_Arr_1%_%Join_ct%
Let>Join_Res=%Join_Res%%Join_tmp%%Join_delimiter%
EndWhile
If>Join_Var_3=0
RegEx>%Join_delimiter%(?=$),Join_Res,0,Matches,NumMatches,1,,Join_Res
Endif
//Get the Result Variable name w/o "" into Join_ResOut_1
RegEx>(?<=^").+(?="$),%Join_var_4%,0,Join_ResOut,N,0
Let>%Join_ResOut_1%=%Join_Res%
END>Join
Re: The Unofficial Macro Scheduler Puzzler #14
hagchr,
Thanks for playing.
I like your concept. The only downside I see is that the request was for the first 10,000 prime numbers and you instead used the ten thousandth prime number as your limiter. Not difficult when the value is provided to you but when the request comes in for the first 1,000,000 prime numbers, you'll have to look up the numbers and figure it out. May not be as easy as it sounds.
On my computer which is an 8 year old i5-4590 with 8 Gb RAM, your script successfully provides all the prime numbers between 1 and 104730 in about 4 minutes and 30 seconds. I took liberties with your script and posted an amended version below. On my computer it successfully completes in 45 seconds.
It seemed to me you only needed one list. I made your sieve list an official array and removed the primes array. The sieve array contains an empty value for each prime number so used that info to generate the list.
As I said, I like your concept.
Thanks for playing.
I like your concept. The only downside I see is that the request was for the first 10,000 prime numbers and you instead used the ten thousandth prime number as your limiter. Not difficult when the value is provided to you but when the request comes in for the first 1,000,000 prime numbers, you'll have to look up the numbers and figure it out. May not be as easy as it sounds.
On my computer which is an 8 year old i5-4590 with 8 Gb RAM, your script successfully provides all the prime numbers between 1 and 104730 in about 4 minutes and 30 seconds. I took liberties with your script and posted an amended version below. On my computer it successfully completes in 45 seconds.
It seemed to me you only needed one list. I made your sieve list an official array and removed the primes array. The sieve array contains an empty value for each prime number so used that info to generate the list.
As I said, I like your concept.
Code: Select all
Timer>start
Let>max=104729
ArrayDim>Sieve,max
Let>i=1
While>i<=max
Add>i,1
If>Sieve_%i%=
Let>j=i
While>j<=max
Add>j,i
Let>Sieve_%j%=TRUE
EndWhile
EndIf
EndWhile
// Join prime array elements to string "resPrimes"
Let>resPrimes=
Let>kk=0
While>%kk%<=%max%
Add>kk,1
Let>value=Sieve_%kk%
If>value=
Let>resPrimes=%resPrimes%%crlf%%kk%
EndIf
EndWhile
Timer>end
Let>time={(%end%-%start%)/60000}
Let>time={(Round(%time%*100)/100)}
MDL>Time: %time% min%CRLF%=====%resPrimes%
Re: The Unofficial Macro Scheduler Puzzler #14
Hi, I agree it is not optimal if you do not know the future primes you are looking for. However, there is a way to estimate how many numbers you need in order to get n prime numbers:
g(n) = nlog(n) + nlog(log(n)), where log is the natural logaritm and n the number of primes you want.
It is a slight overestimation so it should cover the numbers you are looking for.
I adjusted your version so it now asks for how many prime numbers you want, then (slightly over)estimates how many numbers to check and executes. The puzzler question of 10,000 primes took around 1 min. For 100,000 primes, my old pc it needed around 1/2h. The pc did not like the proposition of 1,000,000 - it run out of memory after a while. (I also adjusted so the primes start with 2,3, ... and not 1 as in the latest version).
It will be interesting to see alternative solutions. Can you solve it without looking through the history in each iteration or as in this version "looking through" the whole "future"?
g(n) = nlog(n) + nlog(log(n)), where log is the natural logaritm and n the number of primes you want.
It is a slight overestimation so it should cover the numbers you are looking for.
I adjusted your version so it now asks for how many prime numbers you want, then (slightly over)estimates how many numbers to check and executes. The puzzler question of 10,000 primes took around 1 min. For 100,000 primes, my old pc it needed around 1/2h. The pc did not like the proposition of 1,000,000 - it run out of memory after a while. (I also adjusted so the primes start with 2,3, ... and not 1 as in the latest version).
It will be interesting to see alternative solutions. Can you solve it without looking through the history in each iteration or as in this version "looking through" the whole "future"?
Code: Select all
// Enter number of primes to generate
Label>start
Input>totPrimes,Enter number of primes (>5):,
If>totPrimes=
Exit,r
EndIf
If>totPrimes<6
Goto>start
EndIf
// Estimate number of numbers to check G(n) = n(log(n)+log(log(n)), where log is natural log
Let>tmp1={Ln(%totPrimes%)}
Let>max={Int(%totPrimes%*(%tmp1%+Ln(%tmp1%)))}
Timer>start
ArrayDim>Sieve,max
Let>i=1
While>i<=max
Add>i,1
If>Sieve_%i%=
Let>j=i
While>j<=max
Add>j,i
Let>Sieve_%j%=TRUE
EndWhile
EndIf
EndWhile
// Join prime array elements to string "resPrimes"
Let>resPrimes=
Let>kk=0
Let>ctPrimes=0
While>%kk%<=%max%
Add>kk,1
Let>value=Sieve_%kk%
If>value=
Let>resPrimes=%resPrimes%%crlf%%kk%
Add>ctPrimes,1
// Stop when requested number of primes reached
If>ctPrimes={(%totPrimes%)+1}
Goto>end
EndIf
EndIf
EndWhile
Label>end
// Clean off starting 1
RegEx>(?m-s)^1$\R,resPrimes,0,m,nm,1,,resPrimes
// Find the last prime number and compare with estimate
RegEx>(?m-s)^\d+$\Z,resPrimes,0,m,nm,0
Let>lastPrime=m_1
Let>difference={Round((%max%/%lastPrime%-1)*1000)/10}
Timer>end
Let>time={(%end%-%start%)/60000}
Let>time={(Round(%time%*100)/100)}
MDL>Estimated Number: %max%%CRLF%Actual Number: %lastPrime%%CRLF%Difference: %difference%%%CRLF%%CRLF%Time: %time% min%CRLF%=====%resPrimes%
Re: The Unofficial Macro Scheduler Puzzler #14
@hagchr,
I've not yet examined your latest offering. Hopefully get to it before Monday.
@The World
Here is what I started with. It is as I was taught when these were done longhand using paper and pencil. I believe prime number discovery was an excuse to have a reason to learn how to decipher square roots. The script actually starts at 3 because 2 is an even number and starting there means I either have to prove 2 to be a prime and three to be a prime or I have to check every number rather than every odd number. Shorter code to just say we know they are primes and start with them on the list.
This script "looks through history". It saves a list of prime numbers then checks each upcoming number by dividing it by all the previous prime numbers to see if one of the previous primes is an even divisor. If, after checking all the previous prime numbers, the number is not divisible by any of them without a remainder, the number is prime, and added to the list.
The process is shortened considerably if you first acquire the square root of the number being tested. There is no point in dividing a number by any prime number greater than its square root. You would be testing all the numbers that would have been the answer to a previous division. Waste of time.
I've not yet examined your latest offering. Hopefully get to it before Monday.
@The World
Here is what I started with. It is as I was taught when these were done longhand using paper and pencil. I believe prime number discovery was an excuse to have a reason to learn how to decipher square roots. The script actually starts at 3 because 2 is an even number and starting there means I either have to prove 2 to be a prime and three to be a prime or I have to check every number rather than every odd number. Shorter code to just say we know they are primes and start with them on the list.
I agree. It would be interesting to know if there is a math magic formula for discovering prime numbers.hagchr wrote:It will be interesting to see alternative solutions. Can you solve it without looking through the history in each iteration or as in this version "looking through" the whole "future"?
This script "looks through history". It saves a list of prime numbers then checks each upcoming number by dividing it by all the previous prime numbers to see if one of the previous primes is an even divisor. If, after checking all the previous prime numbers, the number is not divisible by any of them without a remainder, the number is prime, and added to the list.
The process is shortened considerably if you first acquire the square root of the number being tested. There is no point in dividing a number by any prime number greater than its square root. You would be testing all the numbers that would have been the answer to a previous division. Waste of time.
Code: Select all
Let>NumberOfPrimes=10000
Let>Msg_Width=300
Message>Looking for the first %NumberOfPrimes% prime numbers:%crlf%%crlf%Please Wait...
//We know these two are prime and it saves a lot of code
//The place them in the list ahead of time.
Let>vPrimeList=2%crlf%3%crlf%
Let>kk=3
Let>vIntCount=2
While>%vIntCount%<NumberOfPrimes
Add>kk,2
Separate>vPrimeList,crlf,vInt
//Sub>VInt_Count,1
Let>pp=1
Repeat>pp
Add>pp,1
Let>value=vInt_%pp%
If>%pp%<>%vInt_Count%
Let>vAns={%kk% mod %value%}
EndIf
If>%vAns%=0
Let>pp=done
Else
//If>%pp%=%vInt_Count%
If>{%value%>(sqrt(%kk%))}
Let>vPrimeList=%vPrimeList%%kk%%crlf%
Let>vLastPrime=kk
Let>pp=done
EndIf
EndIf
Until>pp=done
Let>vIntCount={%vInt_Count%-1}
Timer>now
Let>now={%now%/1000}
//Enabling the next line gives a readout but takes about 10% longer to run.
SetControlText>Macro Scheduler Message,TMemo,1,Testing %kk%%crlf%Last Found %vLastPrime%%crlf%Total Found %vIntCount%%crlf%Elapsed seconds %now%
EndWhile
MDL>%now% Seconds%crlf%%crlf%%vPrimeList%
Re: The Unofficial Macro Scheduler Puzzler #14
Or was that square root deciphering was a reason to have a book full of prime numbers?Somebody wrote:I believe prime number discovery was an excuse to have a reason to learn how to decipher square roots.
Here we are at the end of October or more precisely the start of November. Its time to announce the "winner" of this well thought out puzzler. This puzzler's accolades go to the only forumite willing to take the time to make and present a prime number generating script. And it is a fine example of prime number generation I might add. Short, fast and accurate. Qualities to which we all aspire.
hagchr!!!
Hopefully, somebody, will at some time in the future, happen across this series of posts and find a use for the script hagchr has presented. And just as important I hope hagchr learned something during his quest. I know I did.
Well done hagchr!!! Thank you once again for your participation!