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