目录
埃氏筛 ( pass even )
埃氏筛 ( char )
埃氏筛 ( bool ) _true is prime
埃氏筛 ( bool ) _false is prime
//
埃氏筛
01 如果 数字 i 没被筛 就可以说明 它是素数 ( 不是2到i-1任何数字的倍数 )
02 试除法判断质数时 循环边界应写成 i <= N/i(1) i <= sqrt(N) 效率较低(2) i*i <= N 当N接近int上限时 i*i 会溢出为负数//
埃氏筛
01 素数a * 素数b 或 素数a * 合数b 结果一定是合数02 因此我们从2开始 将其倍数标记为合数 直到出界03 第二次操作 从未被标记的数中 选取最小的数开始( 该数一定是素数 因为合数存在唯一质数分解 它的质因子使得他一定会在之前被标记 )04 如此循环 未标记的最小数 直到出界埃氏筛 ( pass even )
// 埃氏筛 ( pass even )
typedef long long ll;
const ll MAXN=10005;char judge[MAXN];
ll prime[MAXN];// 0 is prime
void sieve( ll n )
{ll temp=(ll)sqrt(n),i,j;memset( judge,0,sizeof( judge ) );for( i=3;i<=temp;i+=2 ){if( !judge[i] ) for( j=i*i;j<=n;j+=i ) judge[j]=1;}
}ll prime_cnt( ll n )
{ll i,cnt=1;prime[0]=2;for( i=3;i<=n;i+=2 ) if( !judge[i] ) prime[cnt++]=i;return cnt;
}埃氏筛 ( char )
// 埃氏筛 ( char )
typedef long long ll;
const ll MAXN=10005;char judge[MAXN];
ll prime[MAXN];// 1 is prime
ll sieve( ll n )
{ll cnt=0,i,j;memset( judge,1,sizeof( judge ) );// judge[0]=judge[1]=0; for( i=2;i<=n;i++ ){if( judge[i] ) // 起初 默认所有值都为素数{prime[cnt++]=i; // 记录素数 和 素数个数for( j=i*i;j<=n;j+=i ) judge[j]=0; // 筛去 素数 倍数// j=i*i}}return cnt;
}埃氏筛 ( bool ) _true is prime
// 埃氏筛 ( bool )
typedef long long ll;
const ll MAXN=10005;bool judge[MAXN];
ll prime[MAXN];// true is prime
ll sieve( ll n )
{ll cnt=0,i,j;memset( judge,true,sizeof( judge ) );// judge[0]=judge[1]=false; for( i=2;i<=n;i++ ){if( judge[i] ) // 起初 默认所有值都为素数{prime[cnt++]=i; // 记录素数 和 素数个数for( j=i*i;j<=n;j+=i ) judge[j]=false; // 筛去 素数 倍数}}return cnt;}埃氏筛 ( bool ) _false is prime
// 埃氏筛 ( bool )
typedef long long ll;
const ll MAXN=10005;bool judge[MAXN];
ll prime[MAXN];// false is prime
ll sieve( ll n )
{ll cnt=0,i,j;memset( judge,false,sizeof( judge ) );for( i=2;i<=n;i++ ){if( judge[i] ) continue; // true 1 合数prime[cnt++]=i; // 记录素数 和 素数个数for( j=i;j<=n/i;j++ ) judge[ i*j ]=true; // 筛去 素数 倍数}return cnt;
}