9 素数筛
9.1 一般双重筛
通过不断试除来判断某一数字k k k 有无因数
时间复杂度为O ( N 2 ) O(N^2) O ( N 2 )
bool prime ( long long i )
{
if ( i == 2 )
return 1 ;
else if ( i == 1 )
return 0 ;
for ( size_t k = 2 ; k * k <= i ; k ++) {
if ( i % k == 0 ) {
return 0 ;
}
}
return 1 ;
}
int main ()
{
long long n ;
cin >> n ;
for ( size_t i = 2 ; i <= n ; i ++) {
if ( prime ( i )) {
cout << i << endl ;
}
}
return 0 ;
} cpp 换行 复制
9.2 埃拉托斯特尼筛法
核心思路是先标记素数,然后把素数的所有倍数全标记为非素数
时间复杂度是O ( n log log n ) O(n\log{\log{n}}) O ( n log log n )
对于任意一个大于1 1 1 的正整数n,那么它的x x x 倍就是合数(x > 1 x > 1 x > 1 )。利用这个结论,我们可以避免很多次不必要的检测。
如果我们从小到大考虑每个数,然后同时把当前这个数的所有(比自己大的)倍数记为合数,那么运行结束的时候没有被标记的数就是素数了。
vector < int > prime ;
vector < bool > IsPrime ( 1 e 7 );
void Eratosthenes ( long long n )
{
IsPrime [ 0 ] = IsPrime [ 1 ] = 0 ; //前两项不为素数,记作0
for ( size_t i = 2 ; i <= n ; i ++) //先全部记作1
{
IsPrime [ i ] = 1 ;
}
//memset(IsPrime,1,sizeof(IsPrime)); //似乎使用memset的时间复杂度也是O(N)
for ( size_t i = 2 ; i <= n ; i ++)
{
//素数筛选
//从第三项开始,如果这个数被标记为1,就把它记作素数,放入数组
//同时从 i*i 项开始,每次将 i 的倍数标记为非素数
if ( IsPrime [ i ])
{
prime . push_back ( i );
if (( long long ) i * i > n ) continue ; //超过n的不计
for ( size_t j = i * i ; j <= n ; j += i )
{
IsPrime [ j ] = 0 ;
}
}
}
}
int main ()
{
long long n ;
cin >> n ;
Eratosthenes ( n );
for ( auto && i : prime ) cout << i << endl ;
return 0 ;
} cpp 换行 复制
我们可以只筛选到N \sqrt{N} N 来降低操作次数
# include <bits/stdc++.h>
# define endl " \n "
using namespace std ;
vector < int > prime ;
vector < bool > IsPrime ( 1 e 7 );
void Eratosthenes ( long long n )
{
IsPrime [ 0 ] = IsPrime [ 1 ] = 0 ; //前两项不为素数,记作0
for ( size_t i = 2 ; i <= n ; i ++) //先全部记作1
{
IsPrime [ i ] = 1 ;
}
//memset(IsPrime,1,sizeof(IsPrime)); //似乎使用memset的时间复杂度也是O(N)
for ( size_t i = 2 ; i * i <= n ; i ++)
{
//素数筛选
//从 i*i 项开始,每次将 i 的倍数标记为非素数
if ( IsPrime [ i ])
{
for ( size_t j = i * i ; j <= n ; j += i )
{
IsPrime [ j ] = 0 ;
}
}
}
//计入数组
for ( size_t i = 2 ; i <= n ; i ++)
{
if ( IsPrime [ i ])
{
prime . push_back ( i );
}
}
}
int main ()
{
long long n ;
cin >> n ;
Eratosthenes ( n );
for ( auto && i : prime ) cout << i << endl ;
return 0 ;
} cpp 换行 复制
# include <bits/stdc++.h>
# define endl " \n "
using namespace std ;
vector < int > prime ;
vector < bool > IsPrime ( 1 e 7 );
void Eratosthenes ( long long n )
{
IsPrime [ 0 ] = IsPrime [ 1 ] = 0 ; //前两项不为素数,记作0
for ( size_t i = 2 ; i * i <= n ; i ++)
{
//素数筛选
//从 i*i 项开始,每次将 i 的倍数标记为非素数
if (! IsPrime [ i ])
{
for ( size_t j = i * i ; j <= n ; j += i )
{
IsPrime [ j ] = 1 ;
}
}
}
//计入数组
for ( size_t i = 2 ; i <= n ; i ++)
{
if (! IsPrime [ i ])
{
prime . push_back ( i );
}
}
}
int main ()
{
long long n ;
cin >> n ;
Eratosthenes ( n );
for ( auto && i : prime ) cout << i << endl ;
return 0 ;
} cpp 换行 复制
9.3 欧拉筛法
时间复杂度O ( n ) O(n) O ( n )
埃氏筛法仍有优化空间,它会将一个合数重复多次标记。我们可以用改进的筛法欧拉筛来计算
# include <bits/stdc++.h>
# define endl " \n "
using namespace std ;
vector < int > prime ;
vector < bool > not_prime ( 1 e 7 );
void Euler ( long long & n )
{
for ( size_t i = 2 ; i <= n ; i ++)
{
//如果该数标记为 0 即 非(非素数),计入素数数组
if (! not_prime [ i ])
{
prime . push_back ( i );
}
// 换言之,i 之前被 prime[j] 筛过了
// 由于 prime 里面质数是从小到大的,所以 i 乘上其他的质数的结果一定会被
// prime[j] 的倍数筛掉,就不需要在这里先筛一次,所以这里直接 break掉
for ( auto && j : prime )
{
if ( i * j > n ) break ;
not_prime [ i * j ] = 1 ;
if ( i % j == 0 ) break ;
}
}
}
int main ()
{
long long n ;
cin >> n ;
Euler ( n );
for ( auto && i : prime ) cout << i << endl ;
return 0 ;
} cpp 换行 复制