c++素數(shù)篩選法
更新時間：2017年05月30日 11:43:57 作者：傻蝸牛
本文講的是篩選法的C++實現(xiàn)， 篩選法又稱篩法，是求不超過自然數(shù)N（N>1）的所有質(zhì)數(shù)的一種方法。據(jù)說是古希臘的埃拉托斯特尼（Eratosthenes，約公元前274～194年）發(fā)明的，又稱埃拉托斯特尼篩子。
素數(shù)（又稱質(zhì)數(shù)）：指在大于一的自然數(shù)中，只能被1和它自身整除的自然數(shù)；
素數(shù)篩選法是指一種非常規(guī)的素數(shù)判定方法，比較高效率；
原理：任何數(shù)的整數(shù)倍必定不是素數(shù)，大于二的偶數(shù)必定不是素數(shù)。
我們以找出100以內(nèi)的素數(shù)為例，利用原理，我們可以首先排除偶數(shù)是素數(shù)，然后進一步判斷奇數(shù)
實現(xiàn)將偶數(shù)標記為0，素數(shù)標記為1；（也可以用一個bool數(shù)組將偶數(shù)標記為false，奇數(shù)標記為true）
下面是全部代碼
#include <iostream>
#include <cmath>
#define MAX 100
using namespace std;
int main()
{
//設置標記，將偶數(shù)標記為0
int prime[MAX+1];
for(int i=1;i<=MAX;i++)
{
if(i%2==0)
{
prime[i]=0;
}
else prime[i]=1;
}
for(int i=3;i<=sqrt(MAX);i++)
{
if(prime[i]==1)
{
for(int j=i+i;j<=MAX;j=j+i)
{
prime[j]=0;
}
}
}
cout<<"2"<<" ";
for(int i=3;i<=MAX;i++)
{
if(prime[i]==1)
cout<<i<<" ";
}
return 0;
}
相關文章
解決C++ fopen按行讀取文件及所讀取的數(shù)據(jù)問題
今天小編就為大家分享一篇解決C++ fopen按行讀取文件及所讀取的數(shù)據(jù)問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
關于C++智能指針shared_ptr和unique_ptr能否互轉問題
C++中的智能指針最常用的是shared_ptr和unique_ptr，C++新手最常問的問題是我從一個函數(shù)中拿到unique_ptr，但要轉成shared_ptr才能使用，要怎么轉換？同理是否能將shared_ptr轉換成unique_ptr，面對這些問題，跟隨小編一起看看吧2022-05-05
這篇文章主要為大家詳細介紹了OpenCV實現(xiàn)圖像輪廓檢測以及外接矩形，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
這篇文章主要為大家介紹如何利用Matlab制作一款簡單的龍舟小游戲，文中的示例代碼講解詳細，對我們學習Matlab有一定幫助，需要的可以參考一下2022-03-03
這篇文章主要為大家詳細介紹了C語言單鏈表版學生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了C語言代碼中調(diào)用C++代碼的方法示例，文中也介紹了C++代碼調(diào)用C代碼的方法，有需要的朋友可以參考借鑒，下面來一起看看吧。2017-02-02
AVL Tree 是一個「加上了額外平衡條件」的二叉搜索樹，其平衡條件的建立是為了確保整棵樹的深度為O(log_2N)，本文主要介紹了AVL樹的實現(xiàn)，需要的可以參考一下2023-03-03
最近我學習了C++中的模板相關知識，模板是泛型編程的基礎，十分重要。所以特意整理出來一篇文章供我們一起復習和學習2022-08-08
這篇文章主要介紹了深入解析C++編程中線程池的使用,包括線程池的封裝實現(xiàn)等內(nèi)容,需要的朋友可以參考下2015-11-11
這篇文章主要介紹了c語言的形參和實參傳遞的區(qū)別詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-02-02