除了2,3之外的任何质数一定不是2,3的倍数,因此我们可以观察2的倍数和3的倍数之间的一些规律
我们把数字分为|4、5、6|7、8、9|10、11、12|13、14、15|在同一个大小为3的分区内2、3的倍数有
|4、5、6| 2的倍数为4、6 3的倍数为6
|7、8、9| 2的倍数为8、 3的倍数为9
|10、11、12| 2的倍数为10、12 3的倍数为12
|13、14、15| 2的倍数为14 3的倍数为15
由于2、3的最小公倍数为6,故每6个数必然出现一个2和3的共同倍数,我们将其视为3的倍数,上述的结果变为
|4、5、6| 2的倍数为4 3的倍数为6
|7、8、9| 2的倍数为8 3的倍数为9
|10、11、12| 2的倍数为10 3的倍数为12
|13、14、15| 2的倍数为14 3的倍数为15
可以看出当按3位大小分区时,3的倍数一定位于分区的最后一个位置,2的倍数(忽略掉2、3的公倍数)的位置在分区
的第1位和第2位来回交替,呈现出一定规律性,由于质数(>3)一定不是2、和3的倍数,所以其可能出现的位置只能是
分区中除去2、3倍数剩下的位置,第一个这样的数字是5,往后是7、再往后是11、多看几组数我们便可以发现,从5开始,
往后按照2、4、2、4不断交替向前寻找的数一定不是,如何做到2、4交替移动呢,我们可以看出,每移动两次,
移动6个位置,因此当该数 % 6 的余数为1时,前进4,否则前进2即可
static boolean IsPrime(int num) {
if(num == 2 || num == 3 || num == 5) return true;
if(num <= 1 || (num & 1) == 0 || num % 3 == 0) return false;
int i = 5;
int bianjie = (int)Math.sqrt(num)+1;
while(i <= bianjie && (num % i != 0) ) {
i += (i % 6 == 1) ? 4 : 2;
}
return i > bianjie;
}