关于"素数对猜想"的思考

题目如下:

• 题意分析

题目的意思就是对于输入一个给定的数值,找到小于等于它的所有素数,然后在这些素数里面找到相邻的两个数值相差为2的一组数字就是一组"素数对".然后从中遍历找出所有的素数对就可以了.

图片:

代码参考

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
using namespace std;
vector<uint32_t>prime;
/*                 函数说明：
*函数名：void storedPrime(uint32_t &num)
*参数说明：num 无符号32位变量，表示所要求得的质数不超过此值
*函数功能：结合6倍原理实现将不超过num的值存放到vector类型的容器里面
*函数输出：无
*时间复杂度：最坏：O(n^(3/2))  最好：O(n)
*/
void storedPrime(uint32_t &num) //存储小于等于num的素数到容器里面
{
	char flag=0;
	prime.push_back(2);
	prime.push_back(3);
	for (int i = 5; i <= num; i += 2) //观察素数序列,可以发现两个相邻素数之间至少差值为2
	{
		if (i == 5 || i == 7)
		{
			prime.push_back(i);
			continue;
		}
		if (i % 6 != 1 && i % 6 != 5) //不是6的倍数两边的数字,一定不是素数
			continue;
		for (int t = 5; t <= sqrt(i); t += 6) //6两边的数值也可能是5,7,11,13...这样i=l或者i=l+2的倍数,l=5+6k(k为自然数)
		{
			 flag = 0;
			if (i%t == 0 || i % (t + 2) == 0)
			{
				flag = 1;
				break;
			}
		}
		if (flag==1)
			continue;
		prime.push_back(i);
	}
}
int main()
{
	uint32_t num = 0;
	uint32_t count = 0;
	cin >> num;
	if (num < 5) //对于小于5的数字没有素数对
		cout << 0;
	else {
		storedPrime(num); //实现将小于等于num的数值存储到prime容器里面
		for (int i = 1; i < prime.size()-1; i++) //遍历统计素数对的个数
		{
			if (prime[i + 1] - prime[i] == 2)
				count++;
		}
		cout << count;
	}
	//system("pause");
	return 0;
}