您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“C++怎么用埃式篩法求解素?cái)?shù)”的有關(guān)知識(shí),在實(shí)際案例的操作過(guò)程中,不少人都會(huì)遇到這樣的困境,接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細(xì)閱讀,能夠?qū)W有所成!
首先要了解什么式埃式篩法之前,需要知道一個(gè)定理。
就是素?cái)?shù)的整數(shù)倍一定不是素?cái)?shù)。
了解了這個(gè)就基本大概懂了埃式篩法。
首先初始化一個(gè)布爾數(shù)組is_prime,用于記錄每個(gè)數(shù)是否為素?cái)?shù)。
從2開(kāi)始,枚舉每個(gè)數(shù)i,如果is_prime[i]為true,則i是素?cái)?shù),添加到素?cái)?shù)數(shù)組primes中。
然后對(duì)于每個(gè)i,我們讓我擴(kuò)大j倍,直到i*j小于輸入的數(shù)字n,把is_prime[i * j]賦值為false。
重復(fù)步驟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素?cái)?shù)個(gè)數(shù)為" << primes.size() << "個(gè)\n"; end = clock(); cout << "The run time is: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl; return 0; }
運(yùn)行結(jié)果
Code
#include <iostream> #include <vector> #include <ctime> using namespace std; // 埃式篩法求解素?cái)?shù) 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 << "是素?cái)?shù)!!!"; } else { cout << n << "不是素?cái)?shù)..."; } end = clock(); cout << "The run time is: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl; return 0; }
運(yùn)行結(jié)果
“C++怎么用埃式篩法求解素?cái)?shù)”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實(shí)用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。