3.5、算法五（最效率的算法）
质数一般出现在6的倍数两侧，故不在6的倍数的两侧的一定不是质数。
因此，我们将前面的表格进行变换，黑色加粗效果的是6的倍数，红色的是质数，[n]在侧方但不是质数，如下：
| -- | -- | -- | -- | -- | -- |
|---|---|---|---|---|---|
| -- | 0 | 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 | ... | n |
在6的倍数两侧的可能不是质数,因为有可能被n前面的质数整除。
因此，我们将6的倍数两侧的数继续变换，并分解质因数后进行观察。如下：
| -- | -- | -- | -- | -- | -- |
|---|---|---|---|---|---|
5 |
-- | 6 | 7 |
-- | |
11 |
-- | 12 | 13 |
-- | |
17 |
-- | 18 | 19 |
-- | |
23 |
-- | 24 | [25] | 5 x 5 | |
29 |
-- | 30 | 31 |
-- | |
| [35] | 5 x 7 | 36 | 37 |
-- | |
41 |
-- | 42 | 43 |
-- | |
47 |
-- | 48 | [49] | 7 x 7 | |
53 |
-- | 54 | [55] | 5 x 11 | |
59 |
-- | 60 | 61 |
-- | |
| [65] | 5 x 13 | 66 | 67 |
-- | |
71 |
-- | 72 | 73 |
-- | |
| [77] | 7 x 11 | 78 | 79 |
-- | |
83 |
-- | 84 | [85] | 5 x 17 | |
89 |
-- | 90 | [91] | 7 x 13 | |
| [95] | 5 x 19 | 96 | 97 |
-- | |
101 |
-- | 102 | 103 |
-- | |
107 |
-- | 108 | 109 |
-- | |
113 |
-- | 114 | [115] | 5 x 23 | |
| [119] | 7 x 17 | 120 | [121] | 11 x 11 | |
| [125] | 5 x 25 | 126 | 127 |
-- | |
131 |
-- | 132 | [133] | 7 x 19 | |
137 |
-- | 138 | 139 |
-- | |
| [143] | 11 * 13 | 144 | [145] | 5 x 29 | |
149 |
-- | 150 | 151 |
-- | |
| [155] | 5 x 31 | 156 | 157 |
-- | |
| [161] | 7 x 23 | 162 | 163 |
-- | |
167 |
-- | 168 | [169] | 13 * 13 | |
173 |
-- | 174 | [175] | 5 x 35 | |
179 |
-- | 180 | 181 |
-- | |
| [185] | 5 x 37 | 186 | [187] | 11 x 17 | |
191 |
-- | 192 | 193 |
-- | |
197 |
-- | 198 | 199 |
观察发现，比如49，121，169，最大能被其小于等于n的开平方的数整除的，而且这些数肯定是个质数，即可判定其不是质数。
// 在6的倍数两侧的可能不是质数
for (int i = 5; i <= Math.sqrt(number); i += 6) {
if (number % i == 0 || number % (i + 2) == 0) {
result = false;
}
}
