一、定义

质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数整除,换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数

二、相关定理

  • 在一个大于1的数a和它2倍之间(即区间(a, 2a]中)必存在至少一个素数。
  • 存在任意长度的素数等差数列。(格林和陶哲轩,2004年)
  • 一个偶数可以写成两个数字之和,其中每一个数字都最多只有9个质因数。(挪威布朗,1920年)
  • 一个偶数必定可以写成一个质数加上一个合成数,其中的因子个数有上界。(瑞尼,1948年)
  • 一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来,有人简称这结果为 (1 + 5) (中国,1968年)
  • 一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 (1 + 2) (中国陈景润)

三、著名猜想

哥德巴赫猜想:是否每个大于2的偶数都可写成两个素数之和?

孪生素数猜想:孪生素数就是差为2的素数对,例如11和13。是否存在无穷多的孪生素数?

斐波那契数列内是否存在无穷多的素数?是否有无穷多个的梅森素数?在n2与(n+1)2之间是否每隔n就有一个素数?是否存在无穷个形式如X2+1素数?

四、性质

(1)质数p的约数只有两个:1和p。

(2)初等数学基本定理:任一大于1的自然数,要么本身是质数,要么可以分解为几个质数之积,且这种分解是唯一的。

(3)质数的个数是无限的。

(4)质数的个数公式π(n)是不减函数。

(5)若n为正整数,在n的2次方到(n+1)的2次方 之间至少有一个质数。

(6)若n为大于或等于2的正整数,在n到n!之间至少有一个质数。

(7)若质数p为不超过n(n大于等于4)的最大质数,则p>n/2 。

五、著名难题

哥德巴赫猜想

黎曼猜想

孪生质数

梅森质数


六、求质数的方法

1、一般

从2到n-1判断有没有能整除n的数。如果有,则不是素数,否则,是素数

bool is_prime(int n){
    if (n < 2){
        return false;
    }
    int i;
    for (i = 2; i < n; i++){
        if (n%i == 0){
            return false;
        }
    }
    return true;
}

2、优化

从2一直算到sqrt(n),这样算法复杂度降低了很多

bool is_prime(int n){
    if (n < 2){
        return false;
    }
    int i;
    for (i = 2; i*i <= n; i++){
        if (n%i == 0){
            return false;
        }
    }
    return true;
}

3、米勒拉宾素数测试

int tab[]={2, 3, 5, 7};
long long qpow(int a, int b, int r)  //(a^b)%r  快速幂取模
{
    long long ret = 1, tmp = a;
    while(b)
    {
        if (b&1)
            ret = ret*tmp%r;
        tmp = tmp*tmp%r;
        b >>= 1;
    }
    return ret; 
}
bool  Miller_Rabbin(int n, int a)//米勒拉宾素数测试 
{
    int r = 0, s = n-1, j;
    long long k;
    if(n%a == 0)    return false;
    while((s&1) == 0)
    {
        s >>= 1;
        r++;
    }
    k = qpow(a, s, n);
    if(k == 1)  return true;
    for (j = 0; j < r; j++, k=k*k%n)
        if (k == n-1)
            return true;
    return false;
}
bool Isprime(int n)//判断是否是素数 
{
    for (int i = 0; i < 4; i++)
    {
        if (n == tab[i])
            return true;
        if (!Miller_Rabbin(n, tab[i]))
            return false;
    }
    return true;
}

4、普通筛

时间复杂度是O(nloglogn),不足之处在于一个合数可能被筛选多次。

void Prime(){
    memset(tag,0,sizeof(tag));
    tag[0]=tag[1]=1;
    int cnt=0;
    for(int i=2; i*i <= n; i++)
        if(tag[i]==0){
            prime[cnt++]=i;
        for(int j=i+i;j<=n;j+=i)
            tag[j]=1;
    }
}

5、线性筛

时间复杂度为O(n),原因在于每个合数保证只被它最小的那个质因子筛选。关键代码在第10,11行,因为如果i能整出prime[j],那么i肯定是个合数,且i中有质因子肯定小于等于prime[j],所以到此就可以停止了,因为后面的prime[]会比i小的那个质因子要大。

void Prime(){
	memset(tag,0,sizeof(tag));
	int cnt=0;
	tag[0]=tag[1]=1;
	for(int i = 2; i<N; i++){
		if(!tag[i])
			prime[cnt++]=i;
		for(int j=0;j<cnt && prime[j]*i<N; j++){
			tag[i*prime[j]] = 1;
			if(i % prime[j]==0)
				break;
		}
	}
}