我試圖想出一個(gè)方法，它接受一個(gè)整數(shù)并返回一個(gè)布爾值來說明數(shù)字是否為素?cái)?shù)，我不知道多少C; 有人會(huì)關(guān)心給我一些指示嗎？基本上，我會(huì)在C＃中這樣做：static bool IsPrime(int number){ for (int i = 2; i < number; i++) { if (number % i == 0 && i != number) return false; } return true;}
3 回答
狐的傳說
TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超3個(gè)贊
我很驚訝沒有人提到這一點(diǎn)。
使用Eratosthenes的Sieve
細(xì)節(jié)：
除了1和他們自己之外，基本上非主要數(shù)字可以被另一個(gè)數(shù)字整除
因此：非主要數(shù)字將是素?cái)?shù)的乘積。
Eratosthenes的篩子找到一個(gè)素?cái)?shù)并存儲(chǔ)它。當(dāng)檢查新數(shù)字的素?cái)?shù)時(shí)，將根據(jù)已知的素?cái)?shù)列表檢查所有先前的素?cái)?shù)。
原因：
這個(gè)算法/問題被稱為“ 令人尷尬的并行 ”
它創(chuàng)建了一個(gè)素?cái)?shù)集合
它是動(dòng)態(tài)編程問題的一個(gè)例子
它快！
犯罪嫌疑人X
TA貢獻(xiàn)2080條經(jīng)驗(yàn) 獲得超4個(gè)贊
斯蒂芬佳能回答得非常好！
但
通過觀察所有質(zhì)數(shù)的形式為6k±1，除了2和3之外，可以進(jìn)一步改進(jìn)算法。
這是因?yàn)閷?duì)于某些整數(shù)k和i = -1,0,1,2,3或4，所有整數(shù)可以表示為（6k + i）; 2除（6k + 0），（6k + 2），（6k + 4）; 和3分（6k + 3）。
因此，更有效的方法是測(cè)試n是否可被2或3整除，然后檢查所有形式的數(shù)字6k±1≤√n。
這是測(cè)試所有m到√n的3倍。
int IsPrime(unsigned int number) {
if (number <= 3 && number > 1)
return 1; // as 2 and 3 are prime
else if (number%2==0 || number%3==0)
return 0; // check if number is divisible by 2 or 3
else {
unsigned int i;
for (i=5; i*i<=number; i+=6) {
if (number % i == 0 || number%(i + 2) == 0)
return 0;
}
return 1;
}
}
- 3 回答
- 0 關(guān)注
- 515 瀏覽
添加回答
舉報(bào)
0/150
提交
取消