HDU-1262-寻找素数对

红太狼 2022-05-30 11:30 120阅读 0赞

# 寻找素数对 #

## Problem Description ##

哥德巴赫猜想大家都知道一点吧.我们现在不是想证明这个结论,而是想在程序语言内部能够表示的数集中,任意取出一个偶数,来寻找两个素数,使得其和等于该偶数.  
做好了这件实事,就能说明这个猜想是成立的.  
由于可以有不同的素数对来表示同一个偶数,所以专门要求所寻找的素数对是两个值最相近的.

## Input ##

输入中是一些偶整数M(5<M<=10000).

## Output ##

对于每个偶数,输出两个彼此最接近的素数,其和等于该偶数.

## Sample Input ##

20 30 40

## Sample Output ##

7 13 13 17 17 23

这种思想很常用，一个等式，由未知量x1 ○ x2=结果y。如果要找x1和x2但知道结果，如果遍历x1和x2,那么需要双重循环，太费时，现在就是用结果y和其中一个变量x1求另一个变量x2，只需遍历x1这一个就行，就只需一个循环，判断x2是否符合要求即可。

#include <bits/stdc++.h>
    using namespace std;
    #define N 10002
    int prime[N];
    int main()
    {
        int i,j;
        prime[0]=0;
        prime[1]=1;
        prime[2]=1;//筛选法求素数
        for(i=3;i<N;i++)
        {
            if(i%2)
                prime[i]=1;
        else
            prime[i]=0;
        }
        for(i=3;i<=sqrt(N);i++)
            {
                if(prime[i])
                for(j=i+i;j<N;j=j+i)
                prime[j]=0;
            }
        int n,Min,_k;
        while(~scanf("%d",&n))
        {
            Min=10005;
            for(int k=1;k+k<=n;k++)
            {
                if(prime[k]==0)
                    continue;
                if((prime[n-k]==1)&&(Min>=abs(2*k-n)))
                {
                    Min=abs(2*k-n);
                    _k=k;
                }
            }
            printf("%d %d\n",_k,n-_k);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，120人围观）

还没有评论，来说两句吧...

相关阅读

相关 acm 寻找素数对

![这里写图片描述][SouthEast] ![这里写图片描述][SouthEast 1] include <stdio.h> include <windo

落日映苍穹つ/ 2022年07月14日 13:29/ 0 赞/ 130 阅读

相关 hdu 2012 素数判定

素数判定 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

矫情吗；*/ 2022年06月17日 13:18/ 0 赞/ 171 阅读

相关 hdu 3823(素数)

问题描述: Besides the ordinary Boy Friend and Girl Friend, here we define a more academic k

心已赠人/ 2022年05月31日 04:58/ 0 赞/ 78 阅读

相关 HDU-1262-寻找素数对

寻找素数对 Problem Description 哥德巴赫猜想大家都知道一点吧.我们现在不是想证明这个结论,而是想在程序语言内部能够表示的数

红太狼/ 2022年05月30日 11:30/ 0 赞/ 121 阅读

相关寻找素数对

寻找素数对哥德巴赫猜想大家都知道一点吧.我们现在不是想证明这个结论,而是想在程序语言内部能够表示的数集中,任意取出一个偶数,来寻找两个素数,使得其和等于该偶数. 做

偏执的太偏执、/ 2022年05月15日 03:59/ 0 赞/ 157 阅读

相关 HDU2012 素数判定

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

柔光的暖阳◎/ 2022年05月11日 06:40/ 0 赞/ 213 阅读

相关素数对

描述两个相差为2的素数称为素数对，如5和7，17和19等，本题目要求找出所有两个数均不大于n的素数对。输入一个正整数n。1 <= n <= 10000。输出

墨蓝/ 2022年04月10日 10:37/ 0 赞/ 125 阅读

相关 C语言寻找孪生素数

寻找\[m,n\]区间内所有的孪生素数并输出。孪生素数是指差为2的两个素数，例如，3和5，5和7。 ① 编写函数int prime(int n)，判断素数。 ② 编写mai

喜欢ヅ旅行/ 2022年02月20日 13:45/ 0 赞/ 260 阅读

相关 java 寻找素数

素数除了1和它本身无法被其他数整数 1，寻找数组中所含有的素数 class 寻找素数{ public static void main(String

系统管理员/ 2022年01月08日 02:19/ 0 赞/ 182 阅读

相关 HDU4548 美素数

问题链接：[HDU4548 美素数][HDU4548]。基础练习题，用C语言编写程序。问题简述：参见上述链接。问题分析：美素数定义为一个数是素数并且其各位数

淩亂°似流年/ 2021年12月21日 05:34/ 0 赞/ 182 阅读