模板原题
1. 寻找因数筛法
时间复杂度:\(O(n\sqrt n)\)
核心模板代码如下:
bool isprime(int n)
{
if (n < 2) return false; //0和1都不是
for(int i = 2; i * i <= n; ++ i)
if(n % i == 0) return false; //有1和它本身以外的其他因子就不是素数了
return true;
}
2. 埃氏筛法
时间复杂度:\(O(n\log \log n)\)
核心模板代码如下:
void Eratosthenes(int n)
{
vis[0] = vis[1] = true;
for (int i = 2; i <= n; i++)
{
if (!vis[i])
for (int j = 2 * i; j <= n; j += i)
vis[j] = true;
}
for (int i = 1; i <= n; i++)
if (!vis[i])
cout << i << ' ';
cout << '\n';
}
3. 欧拉筛法
时间复杂度:\(O(n)\)
核心思路:
最小质因数 \(\times\) 最大因数(非自己) \(=\) 这个合数
核心模板代码如下:
void getprimes(int n)
{
for (int i = 2; i <= n; i ++)
{
if (!vis[i]) primes[++ cnt] = i;
for (int j = 1; primes[j] * i <= n; j ++)
{
vis[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
标签:log,筛法,int,复杂度,vis,素数,模板
From: https://www.cnblogs.com/ThySecret/p/18523434