【数论】素数

题目描述

给定一个正整数N，求出1到N中有多少个素数。

输入

一个正整数N（N≤10000000）

输出

一行一个整数，表示1到N中有多少个素数。

样例输入

10

样例输出

4

思路分析

本题采用埃拉斯托特尼筛法。该方法是列出所有小素数最有效的方法之一。

原理：从2开始到，将每个素数的各个倍数，标记成合数。

其与试除法不同的关键之处，在于试除法是以素数来测试每个待测数能否被整除。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e7+9;
ll n,ans,p[N];
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(ll i=2;i*i<=n;i++){for(ll j=i*i;j<=n;j+=i){p[j]=1;}}for(ll i=2;i<=n;i++){if(p[i]==0)ans++;}cout<<ans;return 0;
}