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;
}
相關(guān)文章
這篇文章主要為大家詳細介紹了C語言銀行系統(tǒng)課程設計，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了C++獲取任務欄打開程序窗口,大家可以參考使用2013-11-11
這篇文章主要介紹了C語言實現(xiàn)括號匹配的方法，文中代碼簡單易懂，方便大家更好的學習，感興趣的朋友可以參考下2020-06-06
迪杰斯特拉算法(Dijkstra)是由荷蘭計算機科學家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法。本文將用C++實現(xiàn)Dijkstra算法，需要的可以參考一下2022-07-07
這篇文章主要給大家介紹了關(guān)于c語言階乘之和問題的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學習或者使用c語言具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2019-08-08
這篇文章主要為大家詳細介紹了C/C++實現(xiàn)貪吃蛇逐步運動效果的相關(guān)資料，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-05-05
引用是C++一個很重要的特性,顧名思義是某一個變量或?qū)ο蟮膭e名，對引用的操作與對其所綁定的變量或?qū)ο蟮牟僮魍耆葍r,這篇文章主要給大家總結(jié)介紹了C++中引用的相關(guān)知識點,需要的朋友可以參考下2022-05-05
C++中的std::vector是一個動態(tài)數(shù)組（也被稱為可變大小數(shù)組）的容器類,它是C++標準庫提供的其中一種容器類,提供了方便的操作和管理動態(tài)數(shù)組的功能,本文就給大家介紹了C++中vector類的簡單實現(xiàn)代碼,需要的朋友可以參考下2023-08-08
xxx_cast類型轉(zhuǎn)換的實現(xiàn)方法
下面小編就為大家?guī)硪黄獂xx_cast類型轉(zhuǎn)換的實現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
左值引用與指針的區(qū)別：左值引用是一個別名,只能綁定左值,對左值引用的訪問與訪問左值是相同的；指針是一個變量,該變量在內(nèi)存中存在真是的物理地址,該變量內(nèi)的存儲的是一個內(nèi)存地址,訪問指針變量對應的內(nèi)容需要配合解訪問符*2025-03-03