## Suggestion for Fermat prime number sieve

Expand Messages
• 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
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.