Loading ...
Sorry, an error occurred while loading the content.

Suggestion for Fermat prime number sieve

Expand Messages
  • Kermit Rose
    We fill the array with it s index up to the length of the table. For example if we wish to use the Fermat prime number sieve to find the primes
    Message 1 of 1 , Jul 23, 2007
    View Source
    • 0 Attachment
      We fill the array with it's index up to the length of the table.

      For example if we wish to use the Fermat prime number sieve to find the
      primes < 250, we
      set the array to the numbers

      1 2 3 4 5 6 7 8 9 10 11 12 13
      14 15 16 17 18 19 20 21 22 23 24 25
      26 27 28 29 30 31 32 33 34 35 36 37
      38 39 40 41 42 43 44 45 46 47 48 49
      50 51 52 53 54 55 56 57 58 59 60 61
      62 63 64 65 66 67 68 69 70 71 72 73
      74 75 76 77 78 79 80 81 82 83 84 85
      86 87 88 89 90 91 92 93 94 95 96 97
      98 99 100 101 102 103 104 105 106 107
      108 109 110 111 112 113 114 115 116 117
      118 119 120 121 122 123 124 125 126 127
      128 129 130 131 132 133 134 135 136 137
      138 139 140 141 142 143 144 145 146 147
      148 149 150 151 152 153 154 155 156 157
      158 159 160 161 162 163 164 165 166 167
      168 169 170 171 172 173 174 175 176 177
      178 179 180 181 182 183 184 185 186 187
      188 189 190 191 192 193 194 195 196 197
      198 199 200 201 202 203 204 205 206 207
      208 209 210 211 212 213 214 215 216 217
      218 219 220 221 222 223 224 225 226 227
      228 229 230 231 232 233 234 235 236 237
      238 239 240 241 242 243 244 245 246 247
      248 249 250 251 252 253 254 255 256


      Then we zero out 1 since 1 is a unit, and not a prime. We also zero out
      the even numbers of the form 4j + 2 because those numbers are not the
      difference of two squares.

      Now our array looks like this.

      0 2 3 4 5 0 7 8 9 0 11 12 13 0
      15 16 17 0 19 20 21 0 23 24 25 0
      27 28 29 0 31 32 33 0 35 36 37 0
      39 40 41 0 43 44 45 0 47 48 49 0
      51 52 53 0 55 56 57 0 59 60 61 0
      63 64 65 0 67 68 69 0 71 72 73 0
      75 76 77 0 79 80 81 0 83 84 85 0
      87 88 89 0 91 92 93 0 95 96 97 0
      99 100 101 0 103 104 105 0 107 108 109
      0 111 112 113 0 115 116 117 0 119 120
      121 0 123 124 125 0 127 128 129 0 131
      132 133 0 135 136 137 0 139 140 141 0
      143 144 145 0 147 148 149 0 151 152 153
      0 155 156 157 0 159 160 161 0 163 164
      165 0 167 168 169 0 171 172 173 0 175
      176 177 0 179 180 181 0 183 184 185 0
      187 188 189 0 191 192 193 0 195 196 197
      0 199 200 201 0 203 204 205 0 207 208
      209 0 211 212 213 0 215 216 217 0 219
      220 221 0 223 224 225 0 227 228 229 0
      231 232 233 0 235 236 237 0 239 240 241
      0 243 244 245 0 247 248 249 0 251 252
      253 0 255 256


      Now , starting with 9 = 3 * 3, we eliminate candidates as follows.

      zero out position 9
      zero out position 8 = 9 - 1

      zero out position 16
      zero out position 15 = 16 - 1
      zero out position 12 = 15 - 3


      zero out position 25
      zero out position 24 = 25 - 1
      zero out position 21 = 24 - 3
      zero out position 16 = 21 - 5


      zero out position 36
      zero out position 35 = 36 - 1
      zero out position 32 = 35 - 3
      zero out position 27 = 32 - 5
      zero out position 20 = 27 - 7

      zero out position 49
      zero out position 48 = 49 - 1
      zero out position 45 = 48 - 3
      zero out position 40 = 45 - 5
      zero out position 33 = 40 - 7
      zero out position 24 = 33 - 9

      zero out position 64
      zero out position 63 = 64 - 1
      zero out position 60 = 63 - 3
      zero out position 55 = 60 - 5
      zero out position 48 = 55 - 7
      zero out position 39 = 48 - 9
      zero out position 28 = 39 - 11

      zero out position 81
      zero out position 80 = 81 - 1
      zero out position 77 = 80 - 3
      zero out position 72 = 77 - 5
      zero out position 65 = 72 - 7
      zero out position 56 = 65 - 9
      zero out position 45 = 56 - 11
      zero out position 32 = 45 - 13

      zero out position 100
      zero out position 99 = 100 - 1
      zero out position 96 = 99 - 3
      zero out position 91 = 96 - 5
      zero out position 84 = 91 - 7
      zero out position 75 = 84 - 9
      zero out position 64 = 75 - 11
      zero out position 51 = 61 - 13
      zero out position 36 = 51 - 15

      zero out position 121
      zero out position 120 = 121 - 1
      zero out position 117 = 120 - 3
      zero out position 112 = 117 - 5
      zero out position 105 = 112 - 7
      zero out position 96 = 105 - 9
      zero out position 85 = 96 - 11
      zero out position 72 = 85 - 13
      zero out position 57 = 72 - 15
      zero out position 40 = 57 - 17

      zero out position 144
      zero out position 143 = 144 - 1
      zero out position 140 = 143 - 3
      zero out position 135 = 140 - 5
      zero out position 128 = 135 - 7
      zero out position 119 = 128 - 9
      zero out position 108 = 119 - 11
      zero out position 95 = 108 - 13
      zero out position 80 = 95 - 15
      zero out position 63 = 80 - 17
      zero out position 44 = 63 - 19

      zero out position 169
      zero out position 168 = 169 - 1
      zero out position 165 = 168 - 3
      zero out position 160 = 165 - 5
      zero out position 153 = 160 - 7
      zero out position 144 = 153 - 9
      zero out position 133 = 144 - 11
      zero out position 120 = 133 - 13
      zero out position 105 = 120 - 15
      zero out position 88 = 105 - 17
      zero out position 69 = 88 - 19
      zero out position 48 = 69 - 21

      zero out position 196
      zero out position 195 = 196 - 1
      zero out position 192 = 195 - 3
      zero out position 187 = 192 - 5
      zero out position 180 = 187 - 7
      zero out position 171 = 180 - 9
      zero out position 160 = 171 - 11
      zero out position 147 = 160 - 13
      zero out position 132 = 147 - 15
      zero out position 115 = 132 - 17
      zero out position 96 = 115 - 19
      zero out position 75 = 96 - 21
      zero out position 52 = 75 - 23

      zero out position 225
      zero out position 224 = 225 - 1
      zero out position 221 = 224 - 3
      zero out position 216 = 221 - 5
      zero out position 209 = 216 - 7
      zero out position 200 = 209 - 9
      zero out position 189 = 200 - 11
      zero out position 176 = 189 - 13
      zero out position 161 = 176 - 15
      zero out position 144 = 161 - 17
      zero out position 125 = 144 - 19
      zero out position 104 = 125 - 21
      zero out position 81 = 104 - 23
      zero out position 56 = 81 - 25


      zero out position 256
      zero out position 255 = 256 - 1
      zero out position 252 = 255 - 3
      zero out position 247 = 252 - 5
      zero out position 240 = 247 - 7
      zero out position 231 = 240 - 9
      zero out position 220 = 231 - 11
      zero out position 207 = 220 - 13
      zero out position 192 = 207 - 15
      zero out position 175 = 192 - 17
      zero out position 156 = 175 - 19
      zero out position 135 = 156 - 21
      zero out position 112 = 135 - 23
      zero out position 87 = 112 - 25
      zero out position 60 = 87 - 27


      Now we have processed the largest square less than or equal to 256, but
      we are not yet done.

      The next largest square is 289.

      289 - 256 is 33

      The smallest square greater than or equal to 33 is 36

      289 - 36 = 253

      36 = 6 * 6

      2 * 6 + 1 = 13

      zero out position 253
      zero out position 240 = 253 - 13
      zero out position 225 = 240 - 15
      zero out position 208 = 225 - 17
      zero out position 189 = 208 - 19
      zero out position 168 = 189 - 21
      zero out position 145 = 168 - 23
      zero out position 120 = 145 - 25
      zero out position 93 = 120 - 27
      zero out position 64 = 93 - 29

      The next largest square is 324

      324 - 256 = 68

      The smallest square greater than or equal to 68 is 81.

      324 - 81 = 243

      81 = 9 * 9
      2 * 9 + 1 = 19

      zero out position 243
      zero out position 224 = 243 - 19
      zero out position 203 = 224 - 21
      zero out position 180 = 205 - 23
      zero out position 155 = 182 - 25
      zero out position 128 = 157 - 27
      zero out position 99 = 128 - 29
      zero out position 68 = 99 - 31

      The next largest square is 361

      361 - 256 is 105

      The smallest square greater than or equal to 105 is 121 = 11 * 11.

      2 * 11 + 1 = 23

      361 - 121 = 240

      zero out position 240
      zero out position 217 = 240 - 23
      zero out position 192 = 217 - 25
      zero out position 165 = 194 - 27
      zero out position 136 = 167 - 29
      zero out position 105 = 136 - 31
      zero out position 72 = 105 - 33


      The next largest square is 400
      400 - 256 = 144
      The smallest square greater than or equal to 144 is 144 = 12 * 12

      400 - 144 = 256

      2 * 12 + 1 = 25

      zero out position 256
      zero out position 231 = 256 - 25
      zero out position 204 = 231 - 27
      zero out position 175 = 204 - 29
      zero out position 144 = 185 - 31
      zero out position 111 = 164 - 33
      zero out position 76 = 111 - 35

      The next largest square is 441
      441 - 256 = 185
      The smallest square greater than or equal to 185 is 196 = 14 * 14
      2 * 14 + 1 = 29
      441 - 196 = 245

      zero out position 245
      zero out position 216 = 245 - 29
      zero out position 185 = 216 - 31
      zero out position 152 = 185 - 33
      zero out position 117 = 152 - 35
      zero out position 80 = 117 - 37


      The next largest square is 484
      484 - 256 = 228
      The smallest square greater than or equal to 228 is 256 = 16 * 16
      2 * 16 + 1 = 33
      484 - 256 = 228

      zero out position 228
      zero out position 195 = 228 - 33
      zero out position 160 = 193 - 35
      zero out position 123 = 158 - 37
      zero out position 84 = 123 - 39


      The next largest square is 529
      529 - 256 = 273
      The smallest square greater than or equal to 273 is 289 = 17 * 17
      2 * 17 + 1 = 35
      529 - 289 = 240

      zero out position 240
      zero out position 205 = 240 - 35
      zero out position 168 = 205 - 37
      zero out position 129 = 168 - 39
      zero out position 88 = 129 - 41

      The next largest square is 576
      576 - 256 = 320
      The smallest square greater than or equal to 320 is 324 = 18 * 18
      576 - 324 = 252
      2 * 18 + 1 = 37

      zero out position 252
      zero out position 215 = 252 - 37
      zero out position 176 = 215 - 39
      zero out position 135 = 176 - 41
      zero out position 92 = 135 - 43




      The next largest square is 625
      625 - 256 = 369
      The smallest square greater than or equal to 369 is 400 = 20 * 20
      625 - 400 = 225
      2 * 20 + 1 = 41

      zero out position 225
      zero out position 184 = 225 - 41
      zero out position 141 = 184 - 43
      zero out position 96 = 141 - 45


      The next largest square is 676
      676 - 256 = 420
      The smallest square greater than or equal to 420 is 441 = 21 * 21

      676 - 441 = 235
      2 * 21 + 1 = 43

      zero out position 235
      zero out position 192 = 235 - 43
      zero out position 147 = 192 - 45
      zero out position 100 = 147 - 47

      The next largest square is 729
      729 - 256 = 473
      The smallest square greater than or equal to 473 is 484 = 22 * 22
      729 - 484 = 245
      2 * 22 + 1 = 45

      zero out position 245
      zero out position 200 = 247 - 45
      zero out position 153 = 200 - 47
      zero out position 104 = 153 - 49


      The next largest square is 784
      784 - 256 = 528
      The smallest square greater than or equal to 528 is 529 = 23 * 23
      2 * 23 + 1 = 47
      784 - 529 = 255

      zero out position 255
      zero out position 208 = 255 - 47
      zero out position 159 = 208 - 49
      zero out position 108 = 159 - 51


      The next largest square is 841
      841 - 256 = 585
      The smallest square greater than or equal to 585 is 625 = 25*25

      841 - 625 = 216
      2 * 25 + 1 = 51

      zero out position 216
      zero out position 165 = 216 - 51
      zero out position 112 = 165 - 53


      The next largest square is 900
      900 - 256 = 644
      The smallest square greater than or equal to 644 is 676 = 26 * 26

      900 - 676 = 224
      2 * 26 + 1 = 53

      zero out position 224
      zero out position 171 = 224 - 43
      zero out position 116 = 171 - 45

      The next largest square is 961
      961 - 256 = 705
      The smallest square greater than or equal to 705 is 729 = 27 * 27

      961 - 729 = 232
      2 * 27 + 1 = 55

      zero out position 232
      zero out position 177 = 232 - 55
      zero out position 120 = 177 - 37

      The next largest square is 1024
      1024 - 256 = 768
      The smallest square greater than or equal to 768 is 784 = 28 * 28
      1024 - 784 = 240
      2 * 28 + 1 = 57

      zero out position 240
      zero out position 183 = 240 - 57
      zero out position 124 = 183 - 49


      The next largest square is 1089
      1089 - 256 = 833
      The smallest square greater than or equal to 833 is 841 = 29 * 29
      2 * 29 + 1 = 59
      1089 - 841 = 248

      zero out position 248
      zero out position 189 = 248 - 59
      zero out position 128 = 189 - 61


      The next largest square is 1156
      1156 - 256 = 900
      The smallest square greater than or equal to 900 is 900 = 30 * 30
      1156 - 900 = 256
      2 * 30 + 1 = 61

      zero out position 256
      zero out position 195 = 256 - 61
      zero out position 132 = 195 - 63


      The next largest square is 1225
      1225 - 256 = 969
      The smallest square greater than or equal to 969 is 1024 = 32 * 32
      1225 - 1024 = 201
      2 * 32 + 1 = 65

      zero out position 201
      zero out position 136 = 201 - 65





      The next largest square is 1296
      1296 - 256 = 1040
      The smallest square greater than or equal to 1040 is 1089 = 33 * 33
      1296 - 1089 = 207
      2 * 33 + 1 = 67
      zero out position 207
      zero out position 140 = 207 - 67


      The next largest square is 1369
      1369 - 256 = 1113
      The smallest square greater than or equal to 1113 is 1156 = 34 * 34
      1369 - 1156 = 213
      2 * 34 + 1 = 69
      zero out position 213
      zero out position 144 = 213 - 69




      The next largest square is 1444
      1444 - 256 = 1188
      The smallest square greater than or equal to 1188 is 1225 = 35 * 35
      1444 - 1225 = 219
      2 * 35 + 1 = 71

      zero out position 219
      zero out position 148 = 219 - 71


      The next largest square is 1521
      1521 - 256 = 1265
      The smallest square greater than or equal to 1265 is 1296 = 36 * 36
      1521 - 1296 = 225
      2 * 36 + 1 = 73
      zero out position 225
      zero out position 152 = 225 - 73




      The next largest square is 1600
      1600 - 256 = 1344
      The smallest square greater than or equal to 1344 is 1369 = 37 * 37
      1600 - 1369 = 231
      2 * 37 + 1 = 75
      zero out position 231
      zero out position 156 = 231 - 75




      The next largest square is 1681
      1681 - 256 = 1425
      The smallest square greater than or equal to 1425 is 1444 = 38 * 38
      1681 - 1444 = 237
      2 * 38 + 1 = 77
      zero out position 237
      zero out position 160 = 237 - 77


      The next largest square = 1764
      1764 - 256 = 1508
      The smallest square greater than or equal to 1508 is 1521 = 39 * 39
      1764 - 1521 = 243
      2 * 39 + 1 = 79

      zero out position 243
      zero out position 164 = 243 - 79






      The next largest square = 1849
      1849 - 256 = 1593
      The smallest square greater than or equal to 1593 is 1600 = 40 * 40
      1849 - 1600 = 249
      2 * 40 + 1 = 81

      zero out position 249
      zero out position 168 = 249 - 81



      The next largest square =1936
      1936 - 256 = 1680
      The smallest square greater than or equal to 1680 is 1681 = 41 * 41
      1936 - 1681 = 255
      2 * 41 + 1 = 83
      zero out position 255
      zero out position 172 = 255 - 83


      The next largest square = 2025
      2025 - 256 = 1769
      The smallest square greater than or equal to 1769 is 1849 = 43 * 43
      2025 - 1849 = 176

      Now the only composites remaining that are less than or equal to 256 are
      the multiples of 4 greater than 176.

      So zero out the positions of those multiples of four.




      Now we are done.

      The remaining numbers less than 256 are prime.

      Of course, it is fairly easy to make this basic sieve much more efficient.

      The purpose of this example is to make clear the basic process from
      which the theory and program coding can easily be figured out.


      Kermit < kermit@... >
    Your message has been successfully submitted and would be delivered to recipients shortly.