首先，我對C比較陌生，對C 一竅不通，只看了w3schools.org上的C教程，做了一些練習程式。我正在尋找的是一種簡單的東西，它可以在半小時內找到從 1 到 1000000 的所有素數。我不知道如何實作任何復雜的東西，比如阿特金篩法或其他復雜的演算法。您能否更簡單地解釋 Atkin 的 Sieve（如外行的術語）或用 C 演示它？請記住，我剛剛從 w3schools 學習了 C 初學者課程。
我正在使用的代碼如下：
#include <stdio.h>
int n = 0, i, b, e, flag = 0;
int main() {
printf("Enter a positive integer that will be the higher bound: ");
scanf("%d", &b);
for (n = 0; n < b; n ) {
if (n == 0 || n == 1) {
flag = 1;
}
for (i = 2; i <= n / 2; i) {
if (n % i == 0) {
flag = 1;
}
}
if (flag == 0) {
printf("%d is a prime number.\n", n);
} else {
}
flag = 0;
}
return 0;
}
uj5u.com熱心網友回復：
OP 的代碼通過for (i = 2; i <= n / 2; i) {- 適度的第一步來限制因子測驗。
然而，除了 的平方根n之外，沒有任何因子。由于根（通常）比 小n/2，這要快得多。
我們可以使用test_factor * test_factor <= n，但test_factor * test_factor可能會溢位。使用test_factor <= n/test_factor. 智能編譯器將看到附近n/test_factor并n%test_factor發出執行速度與其中一個一樣快的代碼。
代碼可以計算int limit = sqrt(n)，但是 1) 存在邊緣情況問題，因為即使它是整數，sqrt()也可能無法準確double回傳所尋求的根 2) 當整數型別具有比. 3) 產生浮點成本，而 . 幾乎沒有額外成本test_factor <= n/test_factor。
OP 的代碼在找到一個因素時設定一個標志，然后繼續尋找更多。然而，沒有理由繼續尋找。一旦找到一個因素，這會大大加快退出回圈的速度。
我們還可以檢查每個其他值，因為除以 2 的數字不是素數 - 除了一個例外：2。這是一個適度的改進。
bool is_prime(int n) {
if (n % 2 == 0) {
return n == 2;
}
for (int test_factor = 3; test_factor <= n / test_factor; test_factor = 2) {
if (n % test_factor == 0) {
return false;
}
}
return n > 1; // No factors and n is more than 1.
}
采用
for (n = 2; n < b; n ) {
if (is_prime(n)) {
printf("%d is a prime number.\n", n);
}
}
注意：不到 2 秒列印所有小于 1000000 的素數。
對于篩法。請參閱埃拉托色尼篩法偽代碼。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/435877.html
上一篇：C 比較Vector3