Resurrecting a 2000 Year Old Thread

czardas
By czardas in AutoIt Example Scripts,
Some time ago a question came up in General Help and Support about primes. I've always had a fascination with this apparently chaotic number sequence and thought this is a worthwhile challenge. Without reading up on the subject, I set about trying to figure out how I might approach the problem of testing for primality using AutoIt.
 
I started by writing a function which eliminated even numbers, and multiples of 3 and 5. Everything seemed fine at this point; but when I tried to scale up my idea, I took an interesting wrong turn. The approach I had adopted involved testing the primes in the range 7 to 31, and then incrementing them by steps of 30. I had calculated that this would produce a set of numbers guaranteed to include all higher primes. Testing for division using this smaller set of numbers would be faster than testing all the odd numbers ending 1, 3, 7 and 9. At this stage the only thing that seemed obvious to me was - the more prime multiples I skip, the faster my function would run. Here's what I was thinking at the time: to scale this up I need to eliminate a few more prime multiples from a larger sequence and increment by much larger steps. All the numbers in the larger sequences will be made up exclusively of all the higher primes. BUT NOT WITH MY METHOD! This was a fatal oversight on my part.

For a while I was distracted away from coding and this bug went undetected. After a slightly embarrassing moment in the Chat forum I discovered that some prime factors were missing from my sequence ==> 3673. My error was very basic - I had made an assumption without any proof.
  1 * 3 * 5 * 7 * 9 ** 11 ** 13 ** 15 ** 17 ** 19 ** 21 ** 23 ** 25 ** 27 ** 29 ** 31 Odd numbers 1 2 * 4 5 * 7 8 * 10 11 ** 13 14 ** 16 17 ** 19 20 ** 22 23 ** 25 26 ** 28 29 ** ** Factors of 3 1 2 3 4 * 6 7 8 9 ** 11 12 13 14 ** 16 17 18 19 ** 21 22 23 24 ** 26 27 28 29 ** 31 Factors of 5 1 _________ 7 ______ 11 __ 13 ________ 17 __ 19 ________ 23 ______________ 29 __ 31 Sequence ; The sequence created above consists exclusively of prime numbers but the larger sequence generated below contains five extra numbers which are not prime - 121, 143, 169, 187 and 209.; 1 * 3 * 5 * 7 * 9 ** 11 ** 13 ** 15 ** 17 ** 19 ** 21 ** 23 ** 25 ** 27 ** 29 ** 31 ** 33 ** 35 ** 37 ** 39 ** 41 ** 43 ** 45 ** 47 ** 49 ** 51 ** 53 ** 55 ** 57 ** 59 ** 61 ** 63 ** 65 ** 67 ** 69 ** 71 ** 73 ** 75 ** 77 ** 79 ** 81 ** 83 ** 85 ** 87 ** 89 ** 91 ** 93 ** 95 ** 97 ** 99 *** 101 *** 103 *** 105 *** 107 *** 109 *** 111 *** 113 *** 115 *** 117 *** 119 *** 121 *** 123 *** 125 *** 127 *** 129 *** 131 *** 133 *** 135 *** 137 *** 139 *** 141 *** 143 *** 145 *** 147 *** 149 *** 151 *** 153 *** 155 *** 157 *** 159 *** 161 *** 163 *** 165 *** 167 *** 169 *** 171 *** 173 *** 175 *** 177 *** 179 *** 181 *** 183 *** 185 *** 187 *** 189 *** 191 *** 193 *** 195 *** 197 *** 199 *** 201 *** 203 *** 205 *** 207 *** 209 *** 1 2 * 4 5 * 7 8 * 10 11 ** 13 14 ** 16 17 ** 19 20 ** 22 23 ** 25 26 ** 28 29 ** 31 32 ** 34 35 ** 37 38 ** 40 41 ** 43 44 ** 46 47 ** 49 50 ** 52 53 ** 55 56 ** 58 59 ** 61 62 ** 64 65 ** 67 68 ** 70 71 ** 73 74 ** 76 77 ** 79 80 ** 82 83 ** 85 86 ** 88 89 ** 91 92 ** 94 95 ** 97 98 ** 100 101 *** 103 104 *** 106 107 *** 109 110 *** 112 113 *** 115 116 *** 118 119 *** 121 122 *** 124 125 *** 127 128 *** 130 131 *** 133 134 *** 136 137 *** 139 140 *** 142 143 *** 145 146 *** 148 149 *** 151 152 *** 154 155 *** 157 158 *** 160 161 *** 163 164 *** 166 167 *** 169 170 *** 172 173 *** 175 176 *** 178 179 *** 181 182 *** 184 185 *** 187 188 *** 190 191 *** 193 194 *** 196 197 *** 199 200 *** 202 203 *** 205 206 *** 208 209 *** 1 2 3 4 * 6 7 8 9 ** 11 12 13 14 ** 16 17 18 19 ** 21 22 23 24 ** 26 27 28 29 ** 31 32 33 34 ** 36 37 38 39 ** 41 42 43 44 ** 46 47 48 49 ** 51 52 53 54 ** 56 57 58 59 ** 61 62 63 64 ** 66 67 68 69 ** 71 72 73 74 ** 76 77 78 79 ** 81 82 83 84 ** 86 87 88 89 ** 91 92 93 94 ** 96 97 98 99 *** 101 102 103 104 *** 106 107 108 109 *** 111 112 113 114 *** 116 117 118 119 *** 121 122 123 124 *** 126 127 128 129 *** 131 132 133 134 *** 136 137 138 139 *** 141 142 143 144 *** 146 147 148 149 *** 151 152 153 154 *** 156 157 158 159 *** 161 162 163 164 *** 166 167 168 169 *** 171 172 173 174 *** 176 177 178 179 *** 181 182 183 184 *** 186 187 188 189 *** 191 192 193 194 *** 196 197 198 199 *** 201 202 203 204 *** 206 207 208 209 *** 1 2 3 4 5 6 * 8 9 10 11 12 13 ** 15 16 17 18 19 20 ** 22 23 24 25 26 27 ** 29 30 31 32 33 34 ** 36 37 38 39 40 41 ** 43 44 45 46 47 48 ** 50 51 52 53 54 55 ** 57 58 59 60 61 62 ** 64 65 66 67 68 69 ** 71 72 73 74 75 76 ** 78 79 80 81 82 83 ** 85 86 87 88 89 90 ** 92 93 94 95 96 97 ** 99 100 101 102 103 104 *** 106 107 108 109 110 111 *** 113 114 115 116 117 118 *** 120 121 122 123 124 125 *** 127 128 129 130 131 132 *** 134 135 136 137 138 139 *** 141 142 143 144 145 146 *** 148 149 150 151 152 153 *** 155 156 157 158 159 160 *** 162 163 164 165 166 167 *** 169 170 171 172 173 174 *** 176 177 178 179 180 181 *** 183 184 185 186 187 188 *** 190 191 192 193 194 195 *** 197 198 199 200 201 202 *** 204 205 206 207 208 209 *** 1 __________________ 11 __ 13 ________ 17 __ 19 ________ 23 ______________ 29 __ 31 ______________ 37 ________ 41 __ 43 ________ 47 ______________ 53 ______________ 59 __ 61 ______________ 67 ________ 71 __ 73 ______________ 79 ________ 83 ______________ 89 ____________________ 97 _________ 101 ___ 103 ____________107 ___ 109 ___________ 113 ___________________________ 121 ___________________ 127 ___________ 131 ___________________ 137 ___ 139 ___________ 143 ___________________ 149 ___ 151 ___________________ 157 ___________________ 163 ___________ 167 ___ 169 ___________ 173 ___________________ 179 ___ 181 ___________________ 187 ___________ 191 ___ 193 ___________ 197 ___ 199 ___________________________________ 209 ___ ; So there was a big flaw in my reasoning. My earlier assumption that the sequence in my function had to be comprised only of prime numbers was totally wrong. I imagine this may be the cause of amusement to some, but it also goes to show how easy it can be to overlook something fundamental like this. Always check your assumptions are correct and save yourself any future embarrassment!
  Currently untested on an infinite series. ConsoleWrite(_IsPrime(999999937) & @LF & _IsPrime(999999961) & @LF) Func _IsPrime($iNumber) If Not IsInt($iNumber) Then Return SetError(1, 0, False) ; Only integers are allowed $iNumber = Abs($iNumber) If $iNumber = 2 Or $iNumber = 3 Or $iNumber = 5 Or $iNumber = 7 Then Return True If $iNumber < 2 Or Not (Mod($iNumber, 2) And Mod($iNumber, 3) And Mod($iNumber, 5) And Mod($iNumber, 7)) Then Return False Local $nRoot = Sqrt($iNumber) If IsInt($nRoot) Then Return False $nRoot = Floor($nRoot) Static $aFactors[48] = [11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,121,127,131,137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209,211] Local $bPrime = True For $i = 0 To 47 For $j = $aFactors[$i] To $nRoot Step 210 ; = 2 *3 *5 *7 If Mod($iNumber, $j) Then ContinueLoop ; $j is not a factor $bPrime = False ExitLoop 2 Next Next Return $bPrime EndFunc ; _IsPrime
  • 11 replies