今天主要学习了基本的素数算法，包括：素数性判定、埃式是筛选法。
素数性判定
bool is_prime(int n )
{
for ( int i = 2 ; i * i < n ; i++)
{
if ( n % i == 0 ) return false ;
}
return n != 1 ;
}
约数枚举法
vector<int> divsior (int n )
{
vector<int> res ;
for ( int i = 2 ; i * i < n ; i++)
{
if( n % i == 0 )
{
res.push_back(i) ;
if( i != n / i ) res.push_back(n/i) ;
}
}
return false ;
}
素数筛选
int prime[maxn] ; //第i个素数
bool is_prime[maxn+1] ; //素数性判断
int sieve(n)
{
int p = 0 ;
for ( int i = 0 ; i <= n ; i++) is_prime[i] = true ;
is_prime[0] = is_prime[1] = false ;
for ( int i = 2 ; i <= n ; i++)
{
if(is_prime[i])
{
prime[p++] = i ;
for ( int j = 2 * i ; j <= n ; j += i ) is_prime[j] = false ;
}
}
return p ;
}