求素数的方法(实现)
首先记住一点,1不是素数也不是合数
试除法判断是否素数
bool check(int x){
if( x < 2 ) return false ;
for(int i = 2 ; i <= x / i ; i++ )
if( x % i == 0) return false ;
return true ;
}
朴素筛法 找出从2到n的素数
primes存的是素数 cnt表示素数的数量 st表示是否为合数
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
埃氏筛法 找出从2到n的素数
primes存的是素数 cnt表示素数的数量 st表示是否为合数
int primes[N] , cnt ;
bool st[N] ;
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]){
primes[cnt ++ ] = i;
for(int j = i + i ; j <= n ; j += i) st[j] = true;
}
}
}
线性筛法 找出从2到n的素数
primes存的是素数 cnt表示素数的数量 st表示是否为合数
int primes[N] , st[N];
int cnt;
void get_primes(int n) // 线性筛质数
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true; //x=primes[j]*i;x相当于1~n中的任意合数,只会被x的最小质因子primes[j]给筛掉
if (i % primes[j] == 0) break;
//if(i % primes[j] == 0)此时primes[j]一定是i的最小质因子 ,primes[j]一定是primes[j]*i的最小质因子
//if(i % primes[j] != 0) 此时primes[j]一定小于i的所有质因子,primes[j]一定是primes[j]*i的最小质因子
}
}
}