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

左手的ㄟ右手 2022-03-06 11:08 154阅读 0赞

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

# 题目如下:![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjQyODI4_size_16_color_FFFFFF_t_70][] #

*  题意分析

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

图片: ![运行结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjQyODI4_size_16_color_FFFFFF_t_70 1]

代码参考

#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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjQyODI4_size_16_color_FFFFFF_t_70]: /images/20220303/9a6917f288b54cf888012110867dfb94.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjQyODI4_size_16_color_FFFFFF_t_70 1]: /images/20220303/f567fcdaeb80424988f9fdf6337500f1.png