当前位置:首页 > C++知识 > 正文内容

质数(素数)的判断

亿万年的星光3年前 (2021-10-04)C++知识1424


一、定义法

// 1 定义法(除了1和他本身之外,没有任何一个数能被整除)(试除法)
bool is_prime3(unsigned long long n) { //slow
    for (int i = 2; i < n - 1; i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

二、定义法的改进

/*
根据如果一个数是合数,那么它的最小质因数肯定小于等于它的平方根。
用反证法可以证明一下。假设x是n的最小质因数,则存在n/x=p。p>x,x*p=n。如果x不小于等于它的平方根,则x*x>n,而p>x,故x*p>n,假设不成立。合数是与质数相对应的自然数。一个大于1的自然数如果它不是合数,则它是质数。也就是说如果一个数能被它的最小质因数整除的话,那它肯定是合数,即不是质数。所以判断一个数是否是质数,只需判断它是否能被小于它开跟号后的所有数整除,因此,这样做的运算少了很多,降低了时间复杂度。
*/
int isprime(int m)
{
    int i;
    for(i=2;i<=sqrt(m);i++)    /*sqrt(int n)这个函数需要引入math.h头文件*/
      if(m%i==0)
        return 0;
    return 1;
}

三、查表法

把一定范围内的素数都求出来直接复制到数组中,然后查询即可


四、孪生素数

/*
孪生素数: 所谓孪生素数指的是间隔为 2 的相邻素数,它们之间的距离已经近得不能再近了。
若n≥6且n-1和n+1为孪生素数,那么n一定是6的倍数。
证明:
∵ n-1和n+1是素数 ┈┈┈┈┈ ①
∴ n-1和n+1是奇数
∴ n是偶数,即n是2的倍数 ┈┈┈┈┈ ②
假设n不是3的倍数,得:
n=3x+1 或 n=3x+2,
如果n=3x+1,则n-1=3x,与①违背,故n≠3x+1;
如果n=3x+2,则n+1=3(x+1),与①违背,故n≠3x+2;
∴假设不成立,即n是3的倍数,又有②得结论:
n是6的倍数。
 
由上面的规律可以推出下面结论:
若x≧1且n=6x-1或n=6x+1不是素数,那么n一定不是2和3的倍数。
证明:
∵n=6x-1或n=6x+1,即n=2(3x)-1或n=2(3x)+1或n=3(2x)-1或n=3(2x)+1。
∴n一定不是2和3的倍数。
 
素数出现规律:
当n≧5时,如果n为素数,那么n mod 6 = 1 或 n mod 6 = 5,即n一定出现在6x(x≥1)两侧。
证明:
当x≥1时,有如下表示方法:
┈┈ 6x,6x+1,6x+2,6x+3,6x+4,6x+5,6(x+1),6(x+1)+1┈┈
不在6x两侧的数为6x+2,6x+3,6x+4,即2(3x+1),3(2x+1),2(3x+2),它们一定不是素数,所以素数一定出现在6x的两侧。
*/
bool isPrime(int num)
{
    if (num == 2 || num == 3)
        return true;
    if (num % 6 != 1 && num % 6 != 5)
        return false;
    for (int i = 5; i*i <= num; i += 6)
        if (num % i == 0 || num % (i+2) == 0)
            return false;
    return true;
}

五、埃式筛法

首先,将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去。表中剩余的最小数字是3,它不能被更小的数整除,所以是素数。再将表中所有3的倍数全都划去。
依次类推,如果表中剩余的最小数字是m时,m就是素数。然后将表中所有m的倍数全部划去。像这样反复操作,就能依次枚举n以内的素数。

#include<iostream>
using namespace std;
int main() {
	int i,j,n,flag=1;
	bool a[100]= {0};
	for(i=1; i<=100; i++) {
		for(j=2; j<=100; j++) {
			a[i*j]=1;
		}
	}
	for(int p=0; p<=100; p++)
		if(a[p]==0) {
			cout<<a[p]<<" ";
		}
	return 0;
}


六、线性筛法(欧拉筛)

// 由于埃筛法做了许多不必要的循环,所以欧拉筛在埃筛法的基础上,省去了一些步骤,时间复杂度O(n)
int primes(int n)
{
	st[1] = true;
	for(int i=2;i<=n;i++)
	{
		if(!st[i])prime[++k] = i;
		
		for(int j=1;prime[j]<=n/i;j++)
		{
			st[prime[j] * i] = true;
			if(i % prime[j] == 0)break;
		}
	}
	return k; 
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

STL入门——容器2:set

一、简单介绍    set是STL中一个很有用的容器,用来存储同一种数据类型的数据结构(可以称之为K的模型),基本功能与数组相似。set与数组不同的是,在set...

C++中双冒号(::)的用法

一、作用域符号前面一般是类名称,后面一般是该类的成员名称,C++为例避免不同的类有名称相同的成员而采用作用域的方式进行区分如:A,B表示两个类,在A,B中都有成员member。那么A::member就...

【数据结构】队列—基本概念

【数据结构】队列—基本概念

一、基本定义队列是一种先进先出的线性结构,简称FIFO结构。特点就是“先进先出”二、队列的相关概念队头与队尾:允许元素插入的一端称为队尾,允许元素删除的一端称为队头入队:队列的插入操作出队:队列的删除...

【数论】均值不等式

【数论】均值不等式

均值不等式是高中常见的一个知识点,下面这篇文章做一下简单总结。1、其中a,b属于实数R,当且仅当a=b时,等号成立。这个也叫基本不等式2、其中a,b属于正实数,当且仅当a=b时,等号成立。3、其中a,...

2021CSP-J/S全国晋级二轮分数线公布

普及组CSP-J序号省市CSP-J人数CSP-J晋级晋级比例最高分晋级最低分1甘肃13413399.25%86152宁夏10310198.06%65243天津46345197.41%8615.54云南...

【数据结构】并查集1

【数据结构】并查集1

1.引入    对于一个集合S={a1, a2, …, an-1, an},我们还可以对集合S进一步划分: S1,S2,…,Sm-1,Sm,我们希望能够快速确定...