PTA：素数对猜想

柔情只为你懂 2021-09-26 15:30 332阅读 0赞

# 素数对猜想 （20 分） #

--------------------

### 文章目录 ###

*  素数对猜想 （20 分）
 *   *  1. 题目描述
     *  2. 输入格式
     *  3. 输出格式
     *  4. 输入样例
     *  5. 输出样例
     *  6. 解题思路
     *  7. 代码实现
     *  8. 题目来源

--------------------

## 1. 题目描述 ##

> 让我们定义 dn 为：dn = pn+1 − pn，其中 pi 是第 i 个素数。显然有 d1 = 1，且对于 n>1 有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为 2 的素数”。  
> 现给定任意正整数 N (<105)，请计算不超过 N 的满足猜想的素数对的个数。

## 2. 输入格式 ##

> 输入在一行给出正整数 N。

## 3. 输出格式 ##

> 在一行中输出不超过N的满足猜想的素数对的个数。

## 4. 输入样例 ##

> 20

## 5. 输出样例 ##

> 4

## 6. 解题思路 ##

素数对猜想：

>  *  1、正数 2 和 正数 3 是满足题意的第一对素数对；这是特别的一对，不在一下算法范围内；
>  *  2、判断一个正数是否是素数，如果不是，则取下一个正数；
>  *  3、如果这个正数是素数，那么判断 （正数+2） 是否是素数，如果不是，那么取下一个正数；
>  *  4、如果（正数+2）也是素数，那么就是一对满足素数对猜想的一对素数。

素数：

> 一个正数（>2）如果不能被 “2到它的平方根” 之间任何一个正数整除的话，那么它就是一个素数；否则，它不是素数。

## 7. 代码实现 ##

C语言代码如下：

/* 标准输入输出头文件 */
    	#include <stdio.h>
    	#include<math.h>
    	
    	/* 一个自定义函数 */
    	/* 函数功能: 判断传入参数 x 是否是素数 */、
    	/* 参数：整数 x */
    	/* 返回值：如果 x 是素数，返回 1；否则返回 0 */
    	/* 这里假设传入的参数都是合法的 */
    	int primeNumber(long x)
    	{ 
    		/* 返回值，是否是素数的标志 */
    		int isPrimeNumber = 1;
    
    		/* 素数从2开始 */
    		if (x < 2)
    		{ 
    			isPrimeNumber = 0;
    		}
    		/* 2是素数 */
    		else if (2 == x)
    		{ 
    			isPrimeNumber = 1;
    		}
    		else
    		{ 
    			/* 如果 x 能被 2 到 x的平方根 之间的任何一个数整除，则 x 不是素数 */
    			/* 否则，x 是素数 */
    			for (int i = 2; i <= sqrt(x); ++i)
    			{ 
    				if (0 == x % i)
    				{ 
    					isPrimeNumber = 0;
    				}
    			}
    		}
    		return isPrimeNumber;
    	}
    	
    	/* 一个自定义函数 */
    	/* 函数功能：求满足题目要求（素数对猜想）的素数对个数，并输出素数对个数 */
    	/* 参数：最大的整数n，也即是上边界 */
    	/* 这里假设传入的参数都是合法的 */
    	void printPrimeNumberCouple(long n)
    	{ 
    		/* i用于当前待检测是否是素数的数*/
    		/* 并且素数对猜想中，第一对素数是 2 和 3 ，相差1，很特别，踢出去，所以 i 从 5 开始*/
    		int i = 5;
    
    		/* 记录满足条件的素数对的数目 */
    		int primeNumberCoupleCount = 0;
    
    		/* 暗指满足题意的第一对素数对，2和3，单独处理 */
    		if (n >= 3)
    		{ 
    			primeNumberCoupleCount = 1;
    		}
    	
    		/* 后面的素数对相差2 ，并且当前待检测是否是素数的数由i表示 */
    		/* i 和 (i+2) 都不能超过上边界，所以条件是 (i+2) <= n */
    		while (i + 2 <= n)
    		{ 
    			/* 排除第一对素数对之后，如果相差 2 的数满足都是素数，那么就是满足题意的素数对 */
    			/* 素数对数目增加1 ， 待检测的数往后移动2，其实可以是3的 */
    			if (primeNumber(i) && primeNumber(i + 2))
    			{ 
    				++primeNumberCoupleCount;
    				i += 2;
    			}
    			/* 如果当前的数i 和（i+2）不满足要求，取下一个i，那自然有下一个（i+2） */
    			else
    			{ 
    				++i;
    			}
    		}
    		
    		/* 输出满足素数对猜想的素数对数目 */
    		printf("%d\n", primeNumberCoupleCount);
    	}
    	
    	
    	int main()
    	{ 
    		/* N为上边界，从控制台接收输入 */
    		long N = 0;
    		scanf("%ld", &N);
    		printPrimeNumberCouple(N);
    		return 0;
    	}

--------------------

## 8. 题目来源 ##

PTA（Programming Teaching Assistant） [https://pintia.cn/problem-sets/17/problems/261][https_pintia.cn_problem-sets_17_problems_261]  
题目所有版权归 PTA 所有。

[https_pintia.cn_problem-sets_17_problems_261]: https://pintia.cn/problem-sets/17/problems/261