引理:如果 a 是一個大于1的整數,而所有小于或等于根號 a 的素數都除不盡 a ,則 a 是素數。
理想的判斷素數的方法應該是將所有小于或等于根號n的素數去除n,但是n是一個隨機大于1的整數,小于這個數的平方根的素數表不好給定。下面介紹的方法,本意是動態的構建素數表,但是引入了很多冗余的除數。
代碼:
bool prime (int num)


{
if (num == 2 || num == 3 || num == 5)
return true;
if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num == 1)
return false;

unsigned long c = 7;
int maxc = int (sqrt (num));
while (c <= maxc)

{
if (num % c == 0)
return false;
c += 4;
if (num % c == 0)
return false;
c += 2;
if (num % c == 0)
return false;
c += 4;
if (num % c == 0)
return false;
c += 2;
if (num % c == 0)
return false;
c += 4;
if (num % c == 0)
return false;
c += 6;
if (num % c == 0)
return false;
c += 2;
if (num % c == 0)
return false;
c += 6;
}
return true;
}
分析:
相對于sqrt(n)次除,上面的程序需要sqrt(n)*8/30次除,效率提升了15/4倍。
自然數n,我們假設小于n的素數數F(n),F(n)的分布規律為:當n趨向于無窮大時,F(n)/(x/logx) = 1;
所以,動態的冗余度近似為:(sqrt(n)*4/15-x/logx)/sqrt(n)*4/15
其他更好的判斷素數的算法,希望你能給我留言或者寫在評論上,謝謝!
理想的判斷素數的方法應該是將所有小于或等于根號n的素數去除n,但是n是一個隨機大于1的整數,小于這個數的平方根的素數表不好給定。下面介紹的方法,本意是動態的構建素數表,但是引入了很多冗余的除數。
代碼:
bool prime (int num)

{
if (num == 2 || num == 3 || num == 5)
return true;
if (num % 2 == 0 || num % 3 == 0 || num % 5 == 0 || num == 1)
return false;
unsigned long c = 7;
int maxc = int (sqrt (num));
while (c <= maxc)
{
if (num % c == 0)
return false;
c += 4;
if (num % c == 0)
return false;
c += 2;
if (num % c == 0)
return false;
c += 4;
if (num % c == 0)
return false;
c += 2;
if (num % c == 0)
return false;
c += 4;
if (num % c == 0)
return false;
c += 6;
if (num % c == 0)
return false;
c += 2;
if (num % c == 0)
return false;
c += 6;
}
return true;
}分析:
相對于sqrt(n)次除,上面的程序需要sqrt(n)*8/30次除,效率提升了15/4倍。
自然數n,我們假設小于n的素數數F(n),F(n)的分布規律為:當n趨向于無窮大時,F(n)/(x/logx) = 1;
所以,動態的冗余度近似為:(sqrt(n)*4/15-x/logx)/sqrt(n)*4/15
其他更好的判斷素數的算法,希望你能給我留言或者寫在評論上,謝謝!


