素数(C语言/C++)"/>
筛法求素数(C语言/C++)
什么是素数
定义
在大于1的自然数中,除了1和它本身以外不再有其他因数的数称为质数。
C语言实现判断素数
int prime(int x)
{for(int i=2;i*i<=x;i++){if(x%i==0)return 0;}return 1;
}
这个代码应该是很好理解的
但是如果让我们求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);
}
更多推荐
筛法求素数(C语言/C++)
发布评论