我試圖想出一個方法，它接受一個整數并返回一個布爾值來說明數字是否為素數，我不知道多少C; 有人會關心給我一些指示嗎？基本上，我會在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貢獻1804條經驗 獲得超3個贊
我很驚訝沒有人提到這一點。
使用Eratosthenes的Sieve
細節：
除了1和他們自己之外，基本上非主要數字可以被另一個數字整除
因此：非主要數字將是素數的乘積。
Eratosthenes的篩子找到一個素數并存儲它。當檢查新數字的素數時，將根據已知的素數列表檢查所有先前的素數。
原因：
這個算法/問題被稱為“ 令人尷尬的并行 ”
它創建了一個素數集合
它是動態編程問題的一個例子
它快！
犯罪嫌疑人X
TA貢獻2080條經驗 獲得超4個贊
斯蒂芬佳能回答得非常好！
但
通過觀察所有質數的形式為6k±1，除了2和3之外，可以進一步改進算法。
這是因為對于某些整數k和i = -1,0,1,2,3或4，所有整數可以表示為（6k + i）; 2除（6k + 0），（6k + 2），（6k + 4）; 和3分（6k + 3）。
因此，更有效的方法是測試n是否可被2或3整除，然后檢查所有形式的數字6k±1≤√n。
這是測試所有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 關注
- 518 瀏覽
添加回答
舉報
0/150
提交
取消