itsnotluketime 0 Posted April 13, 2016 Share Posted April 13, 2016 expandcollapse popup$okpass = 0 $number = 1 $limit = Int(InputBox( "the limit", "what would you lke to make the limit?")) If $limit < 0 Then Do $limit = Int(InputBox( "the limit", "no negative numbers!")) Until $limit > 0 ElseIf $limit == 0 Then Do $limit = Int(InputBox( "the limit", "only whole numbers, and no letters!")) Until $limit <> 0 EndIf ProgressOn("progress", "calculating primes...") Do ; resets everything each time the number is increased $number += 1 $tempnum = 1 $no = 0 $next = 0 $evencheck = IsInt(number / 2) isprime() $prog = ($number / $limit) * 100 ProgressSet($prog, $number) Until $number >= $limit Func isprime() ; checks to see if the variable is a prime number using a loop, slow with numbers above 5 didgits, but better than nothing If $number <> 2 And $evencheck == 1 Then $no == 1 EndIf If $number > 3 then Do $tempnum += 1 $test = $number / $tempnum If IsInt ( $test ) Then $no = 1 Else $next += 1 EndIf If $next >= ($number / 2) Then FileWrite(@ScriptDir & "\primenumbers.txt", $number & ", ") $no = 1 EndIf Until $no == 1 Else FileWrite(@ScriptDir & "\primenumbers.txt", $number & ", ") EndIf EndFunc ProgressSet(100, "all done!") sleep(5000) Exit Advise for improvements are much appreciated, the script has some efficiency issues atm, its very slow. Link to post Share on other sites

johnmcloud 26 Posted April 13, 2016 Share Posted April 13, 2016 (edited) Local $iBegin, $sPrime = "" Local $iLimit = InputBox("The limit", "What would you lke to make the limit?", 1000) If (Int(StringIsInt($iLimit)) + Int(StringIsFloat($iLimit)) > 0) Then $iBegin = TimerInit() For $x = 1 To $iLimit If _IsPrime($x) Then $sPrime &= $x & ", " Next ConsoleWrite("TIME: " & TimerDiff($iBegin) & @CRLF) EndIf If $sPrime <> "" Then MsgBox(64, "Info", StringTrimRight($sPrime, 2)) Func _IsPrime($iNum) ; Alexander Alvonellos If($iNum < 2) Then Return False If($iNum = 2) Then Return True If(BitAnd($iNum, 1) = 0) Then Return False For $i = 3 To Sqrt($iNum) Step 2 If(Mod($iNum, $i) = 0) Then Return False Next Return True EndFunc ;==>_IsPrime Edited April 13, 2016 by johnmcloud Link to post Share on other sites

czardas 1,269 Posted April 18, 2016 Share Posted April 18, 2016 (edited) Here's a version I wrote. I guess I can improve the code. It was an interesting challenge (the biggest step interval I ever used in a loop = 30030!).https://www.autoitscript.com/forum/topic/158400-resurrecting-a-2000-year-old-thread/?do=findComment&comment=1149851 If you look around the forum you will find more examples: https://www.autoitscript.com/forum/topic/164936-number-is-a-prime-number-challenge/ Edited April 18, 2016 by czardas Pumpkin_30 1 operator64 ArrayWorkshop Link to post Share on other sites

AndyG 50 Posted April 19, 2016 Share Posted April 19, 2016 Hi, Do ; resets everything each time the number is increased $number += 1 $tempnum = 1 $no = 0 $next = 0 $evencheck = IsInt(number / 2) isprime() you should think about what you have written in your comments That´s one of the solutions for your "Speed"-problem. There is no need to calculate every number isprime(). You better should use an algorithm which calculates the primes instead of test them with isprime(). A very fast and simple algorithm is the "Sieve of Eratosthenes"....have fun! Link to post Share on other sites

itsnotluketime 0 Posted April 20, 2016 Author Share Posted April 20, 2016 (edited) Well thanks for the suggestions, I made it like 10x faster by using the square root function, and it now also calculates circle primes (primes that are still primes when their numbers are switched around) which I dont think any other script has done yet! what do you think of it now? expandcollapse popup$okpass = 0 $number = 1 $limit = Int(InputBox( "the limit", "what would you lke to make the limit?")) If $limit < 0 Then Do $limit = Int(InputBox( "the limit", "no negative numbers!")) Until $limit > 0 ElseIf $limit == 0 Then Do $limit = Int(InputBox( "the limit", "only whole numbers, and no letters!")) Until $limit <> 0 EndIf $circle = MsgBox(4, "test", "would you like to also record all the circle primes? circle primes are numbers that are still prime even when their numbers are switched around."); 6 == yes, 7 == no ProgressOn("progress", "calculating primes...") Do $ok = 0 $number += 1 $5check = String($number) $tempnum = 1 $no = 0 $next = 0 $evencheck = IsInt($number / 2) isprime() $prog = ($number / $limit) * 100 ProgressSet($prog, $number) Until $number >= $limit Func isprime() If $number > 5 And StringRight($5check, 1) == 5 Then $no = 1 If IsInt(Sqrt($number)) Then $no = 1 If $number <> 2 And $evencheck == 1 Then $no = 1 EndIf If $number > 3 then Do $tempnum += 1 $test = $number / $tempnum If IsInt ( $test ) Then $no = 1 Else $next += 1 EndIf If $next >= Ceiling(sqrt($number)) Then FileWrite(@ScriptDir & "\primenumbers.txt", $number & ", ") If $circle == 6 Then iscircleprime() $no = 1 EndIf Until $no == 1 Else FileWrite(@ScriptDir & "\primenumbers.txt", $number & ", ") EndIf EndFunc Func iscircleprime() $numstr = String($number) $lastchar = StringRight($numstr, 1) $numstr = StringTrimRight($numstr, 1) $numstr = $lastchar & $numstr $intnum = Number($numstr) $strlen = StringLen($numstr) $nextprime = 0 $done = 0 $up = 1 $notgonnawork = 0 Do $numbercheck = StringRight($numstr, $up) Number($numbercheck) If IsInt($numbercheck / 2) Then $notgonnawork = 1 Else $up += 1 EndIf Until $up >= $strlen Or $notgonnawork == 1 Do $intnum = Number($numstr) $evencheck = IsInt($number / 2) $ctempnum = 1 $ok = 0 $haha = 0 $no = 0 If $number < 10 Then FileWrite(@ScriptDir & "\circleprimes.txt", $number & ", ") $no = 1 $ok = 1 EndIf Do If IsInt(Sqrt($intnum)) Then $no = 1 $ctempnum += 1 $test = $intnum / $ctempnum If IsInt ( $test ) Then $no = 1 Else $haha += 1 EndIf If $haha >= Ceiling(sqrt($intnum)) Then $done += 1 $lastchar = StringRight($numstr, 1) $numstr = StringTrimRight($numstr, 1) $numstr = $lastchar & $numstr $ok = 1 EndIf Until $ok == 1 Or $notgonnawork == 1 If $done == $strlen Then FileWrite(@ScriptDir & "\circleprimes.txt", $number & ", ") $no = 1 EndIf until $no == 1 Or $notgonnawork == 1 EndFunc ProgressSet(100, "all done!") sleep(5000) Exit But I would really like to make it calculate primes then search for the circle primes in the prime numbers txt file, anyone know how I could do this? also sorry AndyG but I could not for the life of me figure out how to use Sieve of Eratosthenes in the script :(. *Edit: added 5 check, its a little faster now **Edit: added thing that instantly rejects numbers that contain an even number in the circle function, its way faster now. Edited April 20, 2016 by itsnotluketime Link to post Share on other sites

czardas 1,269 Posted April 20, 2016 Share Posted April 20, 2016 I took a quick look. I see you are not taking advantage of the fact that all 2+ digit integers ending in 5 are not prime. operator64 ArrayWorkshop Link to post Share on other sites

itsnotluketime 0 Posted April 20, 2016 Author Share Posted April 20, 2016 1 minute ago, czardas said: I took a quick look. I see you are not taking advantage of the fact that all 2+ digit integers ending in 5 are not prime. Did not know that, I'll add it asap, thanks for the suggestion Link to post Share on other sites

czardas 1,269 Posted April 20, 2016 Share Posted April 20, 2016 (edited) Yeah, I went through this logic. 15, 25, 35 etc... are not prime numbers. You can optimize speed by rejecting these numbers instantly. Edited April 20, 2016 by czardas operator64 ArrayWorkshop Link to post Share on other sites

itsnotluketime 0 Posted April 20, 2016 Author Share Posted April 20, 2016 (edited) Just realized that the circle prime functions was seriously flawed, it did not work at all, sorry about that :(, but everything should work fine now. Edited April 20, 2016 by itsnotluketime Link to post Share on other sites

RTFC 391 Posted April 20, 2016 Share Posted April 20, 2016 2 hours ago, czardas said: all 2+ digit integers ending in 5 are not prime A similar trick exists for divisibility by three: Any number is divisible by three if the sum of its individual digits is divisible by three. (So 21 = 2+1 = 3 is divisible by three (7), and 123 = 1+2+3=6 is also divisible by three (41)). czardas 1 My Contributions and Wrappers Spoiler BitMaskSudokuSolver BuildPartitionTable CodeCrypter CodeScanner DigitalDisplay Eigen4AutoIt FAT Suite HighMem MetaCodeFileLibrary OSgrid Pool RdRand SecondDesktop SimulatedAnnealing Xbase I/O Link to post Share on other sites

jchd 1,638 Posted April 20, 2016 Share Posted April 20, 2016 Also by 11: sum of digits in odd position = sum of digits in even position This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe hereRegExp tutorial: enough to get startedPCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta. SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt) Link to post Share on other sites

czardas 1,269 Posted April 20, 2016 Share Posted April 20, 2016 That's cool. Now to formulate the proof (I have a gut feeling there's a really simple proof): failing that I'll cheat and look it up. operator64 ArrayWorkshop Link to post Share on other sites

jchd 1,638 Posted April 20, 2016 Share Posted April 20, 2016 Don't cheat, work it out by yourself for 3 and 11! This is your easy assignment for today czardas 1 This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe hereRegExp tutorial: enough to get startedPCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta. SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt) Link to post Share on other sites

czardas 1,269 Posted April 20, 2016 Share Posted April 20, 2016 (edited) LOL, I have guitar lessons to prepare and teach. I like to cook these kind of ingredients on a slow heat. That's my way! Good tip though! Edit : I think I got it, but you'll have wait for the solution [simple reductionism - starting with the premise that all numbers divisible by 3 are still divisible by 3 after you subtract 3 * 10^n]. Edited April 20, 2016 by czardas operator64 ArrayWorkshop Link to post Share on other sites

RTFC 391 Posted April 20, 2016 Share Posted April 20, 2016 And here are some quick tests for divisibility by primes up to 50 (without proofs ) My Contributions and Wrappers Spoiler BitMaskSudokuSolver BuildPartitionTable CodeCrypter CodeScanner DigitalDisplay Eigen4AutoIt FAT Suite HighMem MetaCodeFileLibrary OSgrid Pool RdRand SecondDesktop SimulatedAnnealing Xbase I/O Link to post Share on other sites

czardas 1,269 Posted April 20, 2016 Share Posted April 20, 2016 (edited) Okay @jchd, you asked for the unschooled approach, and here it is: Prove that when the sum of the digits of a number generate a product of 3, the number itself is also a product of 3.30, 300, 3000 are each divisible by 3 10, 100, 1000 are each 1 higher than a number divisible by 3 20, 200, 2000 are each 1 lower than a number divisible by 3 Premise A If X * 10^n is divisible by 3 then X is divisible by 3 :. trailing zeros can always be stripped leaving the same result 3 is a multiple of 3 1 is 1 higher than a multiple of 3 2 is 1 lower than a multiple of 3 Premise B 3 can always be subtracted from a multiple of 3 leaving a new multiple of 3 9 - 3 = 6 6 - 3 = 3 3 - 3 = 0 In accordance with Premises A and B, all numbers can be reduced to the digits 0, 1 & 2 (by subtracting 3 or 6 from each digit) without changing divisibility by 3. It was shown that adding more zeros does not change the 3 possible outcomes. 01, 1, and 10 are each 1 higher than a number divisible by 3 02, 2, and 20 are each 1 lower than a number divisible by 3 :. zeros can be removed because they have no effect (tricky). The following multi-digit sequences can also be removed (recursively): 12 can be removed repeatedly because it is divisible by 3 [1+2] 21 can be removed repeatedly because it is divisible by 3 [2+1] 111 can be removed repeatedly because it is divisible by 3 [1+1+1] 222 can be removed repeatedly because it is divisible by 3 [2+2+2] If the number ends up with no digits, we have successfully subtracted multiples of 3 (* 10^n) leaving nothing at the end: :. Regardless of size, all the numeric digits had to have added up to a multiple of 3 (in order to end up with nothing), in which case we know that the number we started with must also be divisible by 3. QED (or big leap of faith) Edited April 20, 2016 by czardas operator64 ArrayWorkshop Link to post Share on other sites

## Recommended Posts

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now