傳統(tǒng)方法
傳統(tǒng)的方法是對(duì)于每個(gè) i<a 判斷 if(a%i == 0)? printf("The figure is Prime");
代碼為
? ? for(int i=2; i<=sqrt(a); i++)
? ? {
? ? ? ? if(a%i == 0)? printf("The figure isn't Prime");
? ? }
六倍法
對(duì)于大于等于5的數(shù)字，我們可以用6的倍數(shù)來(lái)表示它继蜡，即摹察，6x-1, 6x, 6x+1, 6x+2, 6x+3, 6x+4的輪回；6x+2 = 2(3x+1), 6x+3 = 3(2x+1), 6x+4 = 2(3x+2), 6x顯然這些并不是素?cái)?shù)鸠匀；那么弦聂，我們可以總結(jié)為钮惠，對(duì)4以上的數(shù)字來(lái)說(shuō)，只有6的倍數(shù)的左右兩位才有可能是素?cái)?shù)橄杨；
因此秘症，我們可以更改循環(huán)為
? ? for(int i=5; i<=sqrt(a), i+=6)
? ? {
? ? ? ? if(a%i == 0 || a%(i+2) == 0) printf("The figure isn't Prime");
? ? }
*1不是素?cái)?shù)
*篩選剩下的是素?cái)?shù)
