c++素?cái)?shù)篩選法
更新時(shí)間：2017年05月30日 11:43:57 作者：傻蝸牛
本文講的是篩選法的C++實(shí)現(xiàn)， 篩選法又稱篩法，是求不超過(guò)自然數(shù)N（N>1）的所有質(zhì)數(shù)的一種方法。據(jù)說(shuō)是古希臘的埃拉托斯特尼（Eratosthenes，約公元前274～194年）發(fā)明的，又稱埃拉托斯特尼篩子。
素?cái)?shù)（又稱質(zhì)數(shù)）：指在大于一的自然數(shù)中，只能被1和它自身整除的自然數(shù)；
素?cái)?shù)篩選法是指一種非常規(guī)的素?cái)?shù)判定方法，比較高效率；
原理：任何數(shù)的整數(shù)倍必定不是素?cái)?shù)，大于二的偶數(shù)必定不是素?cái)?shù)。
我們以找出100以內(nèi)的素?cái)?shù)為例，利用原理，我們可以首先排除偶數(shù)是素?cái)?shù)，然后進(jìn)一步判斷奇數(shù)
實(shí)現(xiàn)將偶數(shù)標(biāo)記為0，素?cái)?shù)標(biāo)記為1；（也可以用一個(gè)bool數(shù)組將偶數(shù)標(biāo)記為false，奇數(shù)標(biāo)記為true）
下面是全部代碼
#include <iostream>
#include <cmath>
#define MAX 100
using namespace std;
int main()
{
//設(shè)置標(biāo)記，將偶數(shù)標(biāo)記為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語(yǔ)言銀行系統(tǒng)課程設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言銀行系統(tǒng)課程設(shè)計(jì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了C++獲取任務(wù)欄打開(kāi)程序窗口,大家可以參考使用2013-11-11
C語(yǔ)言實(shí)現(xiàn)括號(hào)匹配的方法
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)括號(hào)匹配的方法，文中代碼簡(jiǎn)單易懂，方便大家更好的學(xué)習(xí)，感興趣的朋友可以參考下2020-06-06
C++實(shí)現(xiàn)Dijkstra算法的示例代碼
迪杰斯特拉算法(Dijkstra)是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法。本文將用C++實(shí)現(xiàn)Dijkstra算法，需要的可以參考一下2022-07-07
這篇文章主要給大家介紹了關(guān)于c語(yǔ)言階乘之和問(wèn)題的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用c語(yǔ)言具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
C/C++實(shí)現(xiàn)貪吃蛇逐步運(yùn)動(dòng)效果
這篇文章主要為大家詳細(xì)介紹了C/C++實(shí)現(xiàn)貪吃蛇逐步運(yùn)動(dòng)效果的相關(guān)資料，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2016-05-05
引用是C++一個(gè)很重要的特性,顧名思義是某一個(gè)變量或?qū)ο蟮膭e名，對(duì)引用的操作與對(duì)其所綁定的變量或?qū)ο蟮牟僮魍耆葍r(jià),這篇文章主要給大家總結(jié)介紹了C++中引用的相關(guān)知識(shí)點(diǎn),需要的朋友可以參考下2022-05-05
C++中vector類的一些簡(jiǎn)單實(shí)現(xiàn)
C++中的std::vector是一個(gè)動(dòng)態(tài)數(shù)組（也被稱為可變大小數(shù)組）的容器類,它是C++標(biāo)準(zhǔn)庫(kù)提供的其中一種容器類,提供了方便的操作和管理動(dòng)態(tài)數(shù)組的功能,本文就給大家介紹了C++中vector類的簡(jiǎn)單實(shí)現(xiàn)代碼,需要的朋友可以參考下2023-08-08
xxx_cast類型轉(zhuǎn)換的實(shí)現(xiàn)方法
下面小編就為大家?guī)?lái)一篇xxx_cast類型轉(zhuǎn)換的實(shí)現(xiàn)方法。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-12-12
左值引用與指針的區(qū)別：左值引用是一個(gè)別名,只能綁定左值,對(duì)左值引用的訪問(wèn)與訪問(wèn)左值是相同的；指針是一個(gè)變量,該變量在內(nèi)存中存在真是的物理地址,該變量?jī)?nèi)的存儲(chǔ)的是一個(gè)內(nèi)存地址,訪問(wèn)指針變量對(duì)應(yīng)的內(nèi)容需要配合解訪問(wèn)符*2025-03-03