素数筛法分为欧拉筛法
发布时间
阅读量：
阅读量
素数筛法 - 欧拉筛法
素数的筛选方法存在多种，本文重点探讨其中的欧拉筛法
1.暴力法获取素数
时间复杂度为 : O(n²)
若进行一定程度的优化 ：将数据范围由 n 缩减至 √n
相应地，时间复杂度也由 O(n²) 降低至 O(√n)
2.广为人知的埃拉托斯特尼筛法
时间复杂度为 : O(n log log n)
而本次讨论的欧拉筛法则是在埃式筛法的基础上进一步改进
3.欧拉筛法
其时间复杂度为 : O(n)
#include<cstdio>
using namespace std;
int judge[10000]; //保存 这个数是否为素数
int prime[10000]; //用来保存已经找到的素数
int count; //统计素数的个数
int main()
{
int n;
scanf("%d",&n);
for(int i = 2;i <= n;i++)
{
if(!judge[i]) //如果judge[i] 没有被标记为合数
{
prime[count] = i; //将 i 保存进数组全部评论 (0)
还没有任何评论哟~