素数筛
本文最后更新于 2023年2月3日 晚上
素数
素数又称质数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做素数;否则称为合数(规定1既不是质数也不是合数)。
六倍原理
原理:除了2和3以外,其余素数都与6的倍数相邻,也就是也就是说大于3的质数一定满足
用途
忘了筛法的时候可以使暴力写法变得不那么暴力
模板
bool isprime(int n)
{
if (n == 1)
return false;
else if (n == 2 || n == 3)
return true;
//不满足六倍原理,一定不是素数
else if (n % 6 != 1 && n % 6 != 5)
return false;
//只判断6倍的邻数
for (int i = 5; i <= sqrt(n); i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return false;
}
return true;
}
埃氏筛法
原理:要得到自然数
时间复杂度:
有的写法内层循环不同时间复杂度可能是
模板
bool is_prime[1000]; //标记是否是素数
for (int i = 0; i <= n; i++)
is_prime[i] = true; //初始化所有的数为素数
is_prime[1] = false;
for (int i = 2; i <= sqrt(n); i++)
{ //从第一个素数2开始筛选
if (is_prime[i])
{ //如果是素数
for (int j = i * i; j <= n; j += i) //一个小优化,从i * i开始而不是从 i + i开始
{ //则剔除掉它的倍数
is_prime[j] = false;
}
}
}
欧拉筛法(线性筛)
原理:使用埃式筛法时,同一个数字会被筛选多次,比如6先被2筛选一次,再被3筛选一次,这样就浪费了很多的时间。欧拉筛正是埃式筛的优化。即让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。
时间复杂度:
模板
//求小于等于n的素数的个数,并输出每个素数
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5;
int prime[N]; //存素数
bool vis[N]; //保证不做素数的倍数
int main()
{
int n, cnt = 0;
cin >> n;
memset(vis, false, sizeof(vis)); //初始化
memset(prime, 0, sizeof(prime));
for (int i = 2; i <= n; i++)
{
if (!vis[i]) //未被标记
prime[cnt++] = i; //则找到素数
for (int j = 0; j < cnt && i * prime[j] <= n; j++)
{
vis[i * prime[j]] = true; //标记找到的素数的倍数
if (i % prime[j] == 0)
break; //线性的关键!!
}
}
cout << cnt << endl;
for (int i = 0; i < cnt; i++)
cout << prime[i] << " "; //输出每个素数
return 0;
}
个人学习记录,非教程,所以不太注重以上算法原理的解释
素数筛
https://exusiai.top/article/fbadbb2e4f2e.html