repeat_欧氏筛
//
const int MAXN=2e9+10;
bool judge[MAXN];
int prime[MAXN];void sieve( int n )
{int i,j,cnt=0;memset( judge,0,sizeof( judge ) );memset( prime,0,sizeof( prime ) );for( i=2;i<=n;i++ ) // O(n){if( judge[i]==false ) prime[cnt++]=i; // 条件 没被筛就存上for( j=0; j<cnt && prime[j]<=n/i ;j++ ) // 条件 用当前已有素数 + 合数( 素数唯一分解 ) 筛后面的合数{judge[ i*prime[j] ]=true; // 初始为 false 被筛了就 trueif( i%prime[j]==0 ) break;}}
}//
find:
01 O(n) 线性筛
02 忘记咋推导的 回顾最初的 欧氏筛