筛法求素数（C语⾔C++）什么是素数
定义
在⼤于1的⾃然数中，除了1和它本⾝以外不再有其他因数的数称为质数。
C语⾔实现判断素数
int prime(int x)
{
for(int i=2;i*i<=x;i++)
{
if(x%i==0)
return0;
}
c++判断素数
return1;
}
这个代码应该是很好理解的
但是如果让我们求n以内的素数的话，这种⽅法就会很慢
所以请⼤家看下⾯⼀节的内容
筛法求素数
#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string.h>
using namespace std;
bool f[1000005];
int main()
{
int n；
scanf("%d",&n);
f[1]=false;
for(int i=2;i<=n;i++)
f[i]=true;
for(int i=2;i<=n;i++)
{
if(f[i]==true)
{
for(int j=2;j*i<=n;j++)
f[i*j]=false;
}
}
for(int i=2;i<=n;i++)
if(f[i])
printf("%d ",i);
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。