AcWing 868. 筛质数
原题链接
简单
作者:
阿飞被注册了
,
2021-05-06 22:19:31
,
所有人可见
,
阅读 336
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
bool str[N];
int primes[N];
int prime(int n)
{
int cnt = 0;
for(int i = 2; i <= n; i++)
{
if(!str[i])
{
primes[cnt++] = i;
// str[i] = true;
}
//这里的变界改为: j < cnt时 当j==cnt-1,primes[cnt-1] * i 可能>n,下面的str[primes[j]*i]就会越界!!
//边界为 primes[j] <= n / i时,primes[j] * i <= n,下面的str不会越界发生段错误
for(int j = 0; primes[j] <= n / i; j++)
{
str[primes[j] * i] = true;
if(i % primes[j] == 0)
break;
//如果不break,j 就会一直加,导致越界。
}
}
return cnt;
}
int main()
{
int n;
cin >> n;
int t = prime(n);
cout << t;
}