資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 查詢質數的最快速演算法是什麼？
埃拉托色尼篩法是最有效的方法之一，用於找出小於 n 的質數，其中 n 小於 1000 萬左右。
如下所示，展示了埃拉托色尼篩法的程式。
示例
#include <bits/stdc++.h>
using namespace std;
void SieveOfEratosthenes(int num) {
bool pno[num+1];
memset(pno, true, sizeof(pno));
for (int i = 2; i*i< = num; i++) {
if (pno[i] == true) {
for (int j = i*2; j< = num; j + = i)
pno[j] = false;
}
}
for (int i = 2; i< = num; i++)
if (pno[i])
cout << i << " ";
}
int main() {
int num = 15;
cout << "The prime numbers smaller or equal to "<< num <<" are: ";
SieveOfEratosthenes(num);
return 0;
}輸出
上述程式的輸出如下所示。
The prime numbers smaller or equal to 15 are: 2 3 5 7 11 13
現在，讓我們瞭解一下上述程式。
函式 SieveOfEratosthenes() 找到所有早於作為引數提供的 num 的質數。為此給出的程式碼片段如下所示。
void SieveOfEratosthenes(int num) {
bool pno[num+1];
memset(pno, true, sizeof(pno));
for (int i = 2; i*i< = num; i++) {
if (pno[i] == true) {
for (int j = i*2; j< = num; j + = i)
pno[j] = false;
}
}
for (int i = 2; i< = num; i++)
if (pno[i])
cout << i << " ";
}函式 main() 設定 num 的值，然後打印出所有小於或等於 num 的質數。透過呼叫函式 SieveOfEratosthenes() 來完成此操作。為此給出的程式碼片段如下所示。
int main() {
int num = 15;
cout << "The prime numbers smaller or equal to "<< num <<" are: ";
SieveOfEratosthenes(num);
return 0;
}
更新於:2020 年 6 月 26 日
3K+ 瀏覽次數
廣告