首页 > 代码库 > 埃拉托色尼筛法（Sieve of Eratosthenes）求素数。
埃拉托色尼筛法（Sieve of Eratosthenes）求素数。
埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数的方法。
从建立一个整数2~N的表着手，寻找i? 的整数，编程实现此算法，并讨论运算时间。
由于是通过删除来实现，而1和0则不是素数，所以从2，3，5以及其倍数删除。
用Data[]来储存所有的数，将替换好的数字存在Data[]当中
而只需做出将2，3，5以及能将这些数整除的数字替换为零：if（Data[j] % i == 0 ） Data[j]==0;
实现的代码段为：
for (i = 2; i < n; i++) for (j = i + 1; j < n; j++) if (Data[j] != 0 && Data[j] % i == 0) Data[j] = 0;
所以最终完整的实现过程是：
#include <iostream>
#include <math.h>
using namespace std;
#define Max 50000
int n;
int Data[Max];
class Rox
{
public:
void Show();
void Creat();
void Run();
private:
int i, j;
};
void Rox::Creat()
{
for (i = 0; i <= n; i++)
Data[i] = i;
}
void Rox::Run()
{
for (i = 2; i < n; i++){
for (j = i + 1; j < n; j++){
if (Data[j] != 0 && Data[j] % i == 0)
Data[j] = 0;
}
}
}
void Rox::Show()
{
for (i = 0; i <=n; i++)
{
if (Data[i] != 0&&Data[i]!=1)
cout <<" " <<Data[i];
}
}
void main()
{
Rox T;
cout << "请输入所测试的最大值 N:";
cin >> n;
T.Creat();
cout << "所创建的表为" << endl;
T.Show();
T.Run();
cout<<endl;
cout << "经过删除得到的表为:" << endl;
T.Show();
cout << endl;
}
埃拉托色尼筛法（Sieve of Eratosthenes）求素数。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。