首先要了解什么式埃式筛法之前,需要知道一个定理。
就是素数的整数倍一定不是素数。
了解了这个就基本大概懂了埃式筛法。
Code
#include <iostream> #include <vector> #include <ctime> using namespace std; vector <int> sieve_of_eratosthenes(int n) { vector <int> primes; vector <bool> is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; i++) { if (is_prime[i]) { primes.push_back(i); } for (int j = 2; i * j <= n; j++) { is_prime[i * j] = false; } } return primes; } int main() { clock_t start, end; start = clock(); int n; cout << "Please Enter n: "; cin >> n; vector <int> primes = sieve_of_eratosthenes(n); cout << "Primes: "; for (int prime : primes) { cout << prime << " "; } cout << "\n素数个数为" << primes.size() << "个\n"; end = clock(); cout << "The run time is: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl; return 0; }
运行结果
Code
#include <iostream> #include <vector> #include <ctime> using namespace std; // 埃式筛法求解素数 bool sieve_of_eratosthenes(int n) { vector <bool> is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; for (int i = 2; i <= n; i++) { if (is_prime[i] && i == n) { return true; } for (int j = 2; i * j <= n; j++) { is_prime[i * j] = false; if (i * j == n) { return false; } } } } int main() { clock_t start, end; start = clock(); int n; cout << "Please Enter n: "; cin >> n; if (sieve_of_eratosthenes(n)) { cout << n << "是素数!!!"; } else { cout << n << "不是素数..."; } end = clock(); cout << "The run time is: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl; return 0; }
运行结果