本篇内容介绍了“C++怎么用埃式筛法求解素数”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!
首先要了解什么式埃式筛法之前,需要知道一个定理。
就是素数的整数倍一定不是素数。
了解了这个就基本大概懂了埃式筛法。
首先初始化一个布尔数组is_prime,用于记录每个数是否为素数。
从2开始,枚举每个数i,如果is_prime[i]为true,则i是素数,添加到素数数组primes中。
然后对于每个i,我们让我扩大j倍,直到i*j小于输入的数字n,把is_prime[i * j]赋值为false。
重复步骤2和3,直到遍历到n为止。
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; }
运行结果
“C++怎么用埃式筛法求解素数”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。