AcWing 868. 质数筛法
原题链接
简单
筛质数
输入样例
8
输出样例
4
埃氏筛法
代码
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include <stdbool.h>
#define ll long long
bool is_prime[1000010];
int cnt=0,prime[1000010];
void get_prime(int n)
{
for (int i = 0; i <= n; i++)
is_prime[i] = true;
is_prime[0] = is_prime[1] = false; //0和1都不是素数
for (int i = 2; i <= n; i++)
{
if (is_prime[i])
{
prime[cnt++] = i;//记录这个质数
for (int j = 2 * i; j <= n; j+=i)//该质数的倍数都不是质数
is_prime[j] = false;
}
}
}
int main()
{
int n;
scanf("%d", &n);
get_prime(n);
printf("%d", cnt);
return 0;
}
欧拉筛法
代码
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include <stdbool.h>
#define ll long long
bool is_prime[1000010];
int cnt=0,prime[1000010];
/*核心:每一个合数仅会被其最小质因子筛去*/
void get_prime(int n)
{
for (int i = 0; i <= n; i++)
is_prime[i] = true;
is_prime[0] = is_prime[1] = false; //0和1都不是素数
for (int i = 2; i <= n; i++)
{
if (is_prime[i])
prime[cnt++] = i;
for (int j = 0; /*j<cnt&&*/prime[j] <= n / i; j++)
//对于任意一个合数x,假设pj为其最小质因子,在i<x/pj时,一定会被筛掉
{
is_prime[prime[j] * i] = false;
if (i % prime[j] == 0)//保证pj一定是i的最小质因子
break;// 说明i以前被之前的筛过了,就不必重复筛
}
}
}
int main()
{
int n;
scanf("%d", &n);
get_prime(n);
printf("%d", cnt);
return 0;
}