HDU-1262-寻找素数对

红太狼 2022-05-30 11:30 167阅读 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 条评论，167人围观）

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

相关阅读

相关实现寻找最小的素数对算法（Java）

实现寻找最小的素数对算法（Java）在这篇文章中，我们将探讨如何使用Java编写一个算法来寻找最小的素数对。素数对是一对相邻的素数，它们之间的差值为2。我们将使用一种简单但

谁践踏了优雅/ 2023年10月15日 15:22/ 0 赞/ 36 阅读

相关【Java】寻找素数

![在这里插入图片描述][d75c9d68c49a4b25830fd3376f167a45.png] 什么是素数？如何求素数？ ![在这里插入图片描述][ce5d29

蔚落/ 2023年09月26日 11:11/ 0 赞/ 25 阅读

相关 acm 寻找素数对

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

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

相关 hdu 3823(素数)

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

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

相关 HDU-1262-寻找素数对

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

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

相关寻找素数对

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

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

相关 HDU2012 素数判定

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

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

相关素数对

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

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

相关 C语言寻找孪生素数

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

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

相关 java 寻找素数

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

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