线性（欧拉）筛法筛素数表

素数表的普通筛法

一个合数可以表示成一个素数和一个其他数的乘积，即假设有合数A，那么一定存在这样的A = b * c，其中b和c
有一个为素数，由此得到以下的方法，从2—maxn循环一遍，每次筛掉 i 与素数表每一项的乘积，最终剩下的就是素数。

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 100;
bool isprime[maxn+1];
int primetable[maxn+1], ptr;
void mktable()
{
ptr = 0;
memset(isprime,true,sizeof isprime);
for (int i=2; i<=maxn; i++)
{
if (isprime[i] == true)
primetable[ptr++] = i;
for (int j=0; j<ptr&&i*primetable[j]<=maxn; j++)
isprime[i*primetable[j]] = false;
}
}
int main()
{
mktable();
for(int i=0; i<ptr; i++)
cout << primetable[i] << ' ';
return 0;
}

线性筛法（欧拉筛法）

虽然上述方法可以达到筛出素数的目的，但是举一个简单例子，12 = 2 * 6， 12 = 3 * 4，对于 i = 4， 12会被筛掉一次，对于 i = 6，12也会被筛掉一次，也就是说上面的方法存在重复判断，对于maxn比较大的时候效率比较低。
线性筛法的原理可以解释成这个样子：
对于一个合数A，一定存在这样的表示 A = b * c；其中b或c为质数，不妨假设c为质数，则b存在两张可能，质数或者合数，若b为合数，存在x， y（假设x为质数，y任意）使得 b = x * y； 那么 A = (x * y) * c，即 A = x * （y * c）。显然质数x比质数c要小，也就是一个合数与一个质数的乘积可以表示为一个更大的合数与一个更小的质数的乘积。当 i = 4时，4%2 = 0，也就是比2大的质数与4相乘都可以化成2 * 某个数
线性筛法比普通筛法多了一个判断

if (i%primetable[j] == 0)
break;

完整代码：

#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 100;
bool isprime[maxn+1];
int primetable[maxn+1], ptr;
void mktable()
{
ptr = 0;
memset(isprime,true,sizeof isprime);
for (int i=2; i<=maxn; i++)
{
if (isprime[i] == true)
primetable[ptr++] = i;
for (int j=0; j<ptr&&i*primetable[j]<=maxn; j++)
{
isprime[i*primetable[j]] = false;
if (i%primetable[j] == 0)
break;
}
}
}
int main()
{
mktable();
for(int i=0; i<ptr; i++)
cout << primetable[i] << ' ';
return 0;
}

最后

以上就是明亮斑马为你收集整理的线性（欧拉）筛法筛素数表的全部内容，希望文章能够帮你解决线性（欧拉）筛法筛素数表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。