侧边栏壁纸
  • 累计撰写 25 篇文章
  • 累计创建 11 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

素数的判定

LinJHS
2022-11-16 / 0 评论 / 0 点赞 / 16 阅读 / 6154 字 / 正在检测是否收录...

素数的判定

这个是挺早之前的了,发现没有更新到文档里,那就浅浅水一篇(主要是群友都在 push)(我的笔记还可以水超级多篇)。归档到这里,方便以后拿板子。

简介

素数又称质数,是指一个大于 ​1 的正整数,如果除了 ​1 和它本身以外,没有其他的约数,例如 ​2,3,5,7,3021377 等,反之就是合数。​1 既不是素数也不是合数。

素数就像整数世界里的原子,整个整数世界都是由这些素数原子组成的,比如 ​15=3\times 5​121=11\times 11 等等。有关素数的问题是数论研究的主要课题,我国著名数学家华罗庚教授及陈景润、王元研究员、潘承洞教授等对素论的研究都有重要贡献.

早在 2000 多年前的古希腊,伟大的数学家欧几里德就用反证法证明了:素数有无穷多个。在他的不朽名著《几何原本》第四卷命题 20 中是这样叙述的:预先给定几个素数,则有比他们更多的素数。他是这样证明的:设 ​a,b,c 是给定的素数,构造一个新的数 ​t=a\times b\times c+1 ,则已有的素数 ​a,b,c 均不能整除 ​t ,所以要么 ​t 本身就是素数,此时 ​t 不等于 ​a,b,c 中任意一个数;要么 ​t 能被不同于 ​a,b,c 的某一个素数整除,因此必然存在一个素数力不同于已有的素数 ​a,b,c 。例如:​2\times 3\times 5+1=31,3\times 5\times 7+1=106=2\times 53 。也就是说,有了 ​n 个素数,就可以构造出第 ​n+1 个素数,因此素数有无穷多个。

埃式筛法

对于数据范围比较大的情况下,需要找出所有素数,可以采用“筛选法”求出“素数
表”。具体方法如下:

  1. 先将 ​2\sim N 之间的所有数写在纸上:

    ​2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24\cdots

  2. ​2 的上面画一个圆圈,然后划去 ​2 的其他倍数;

  3. 第一个既未画圈又没有被划去的数是 ​3,将它画圈,再划去 ​3 的其他倍数;

  4. 现在既未画圈又没有被划去的第一个数是 ​5 ,将它画圈,并划去 ​5 的其他倍数……

  5. 依次类推,一直到所有小于或等于 ​N 的各数都画了圈或划去为止。这时,表中画了圈的以及未划去的那些数正好就是小于 ​N 的素数。实现代码如下:

//埃式筛法
#include <bits/stdc++.h>
using namespace std;

bool isprime[10000000];

void sieve(int n)
{
	memset(isprime,true,sizeof(isprime));
	for(int i=2;i*i<=n;i++)
	{
		if(isprime[i])
		{
			for(int j=i*i;j<=n;j+=i)
				if(isprime[j])
					isprime[j]=false;
		}
	}
} 

int main()
{
	int n;
	scanf("%d",&n);
	sieve(n);
	for(int i=2;i<=n;i++)
		if(isprime[i])
			printf("%d ",i);
	return 0;
}

欧拉筛法

仔细分析上述代码发现,这种方法会造成重复筛除合数,影响效率。比如 ​30 ,在 ​i=2 的时候,​k=2\times 15 筛了一次;在 ​i=5,k=5\times 6 的时候又筛了一次。所以,也就有了“快速线性筛法”。快速线性筛法没有冗余,不会重复筛除一个数,所以“几乎”是线性的,虽然从代码上分析,时间复杂度并不是 O(n) 。先看实现代码:

//欧拉筛法
#include <bits/stdc++.h>
using namespace std;

bool isprime[10000000];
int prime[5000000];

void Euler_sieve(int n)
{
	memset(isprime,true,sizeof(isprime));
	prime[0]=0;
	for(int i=2;i<=n;i++)
	{
		if(isprime[i])
			prime[++prime[0]]=i;
		for(int j=1;j<=prime[0] && i*prime[j]<=n;j++)
		{
			isprime[i*prime[j]]=false;
			if(i%prime[j]==0)
				break;
		}
	}
} 

int main()
{
	int n;
	scanf("%d",&n);
	Euler_sieve(n);
	for(int i=1;i<=prime[0];i++)
		printf("%d ",prime[i]);
	return 0;
}

首先,先明确一个条件,任何合数都能表示成一系列素数的积。

  1. 如果 ​i 是素数的话,那简单,一个大的素数 ​i 乘以不大于 ​i 的素数,这样筛除的数跟之前的是不会重复的。筛出的数都是 ​n=p_1\times p_2的形式,​p_1​p_2 不相等;
  2. 如果 ​i 是合数,此时 ​i 可以表示成递增素数相乘 ​i=p_1\times p_2\times \cdots \times p_n​p_i 都是素数 ​(2\leq i\leq n),p_i\leq p_j(i\leq j)​p_1 是最小的系数。

根据上述代码,当 ​p_1==\text{prime}[j] 的时候,筛除就终止了,也就是说,只能筛出不大于 ​p_1 的质数​\times i

我们可以直观地举个例子。​i=2\times 3\times 5 ,此时能筛除 ​2\times i,不能筛除 ​3\times i ,如果能筛除 ​3\times i 的话,当 ​i'=3\times 3\times 5 时,筛除 ​2\times i' 就和前面重复了。

当然,还有 2 个结论是可以证明的:

  1. 一个数不会被重复筛除;
  2. 合数肯定会被筛除。

参考资料:

  1. 林厚从《信息学奥赛 之 数学一本通》
0

评论区