埃氏筛法

xiaoxiao2021-02-28  6

##埃氏筛法 枚举一段区间的素数。

#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<vector> #include<map> using namespace std; const int maxn = 1e5+5; typedef long long ll; int n; int prime[maxn]; bool is_prime[maxn]; int sieve(int n) { for(int i=0;i<=n;i++) is_prime[i] = true; is_prime[0] = is_prime[1] = false; int num = 0; for(int i=2;i<=n;i++) { if(is_prime[i]) { prime[num++] = i; for(int j=2*i;j<=n;j+=i) { is_prime[j] = false; } } } return num; } int main() { scanf("%d",&n); int ans = sieve(n); printf("%d\n",ans); return 0; }
转载请注明原文地址: https://www.6miu.com/read-1600220.html

最新回复(0)