首页 > 试题广场 >

查找组成一个偶数最接近的两个素数

[编程题]查找组成一个偶数最接近的两个素数
  • 热度指数：168414 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}对于给定的偶数 n，找出两个素数 a,b，满足：
\hspace{23pt}\bullet\,它们的和等于 n；
\hspace{23pt}\bullet\,它们的差值的绝对值最小。

\hspace{15pt}我们可以证明，a,b 一定存在，从小到大输出满足条件的素数对。

输入描述:
\hspace{15pt}输入一个整数 n \left(4 \leqq n \leqq 10^3\right)。保证 n 是偶数。


输出描述:
\hspace{15pt}第一行输出一个整数 a，代表满足条件的素数对中的较小者。
\hspace{15pt}第二行输出一个整数 b，代表满足条件的素数对中的较大者。
示例1

输入

20

输出

7
13
示例2

输入

4

输出

2
2
算法知识视频讲解
添加回答
C
人生有三乐头像 人生有三乐
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {

    //数论肯定有规律，因为是求和，所以a肯定是小于n/2，b肯定大于n/2的，这样的和才会等于n。然后a从n/2递减找，b从n/2递增开始找，这样它们的差值绝对值才会最小
    //对于找素数，因为是求乘积，所以它的约数肯定是小于平方根的，因为约数的另一个数，肯定是大于平方根的约数。

    int n;
    scanf("%d",&n);

    int n2=n/2; //避免重复计算

    for (int i=0; (n2-i)>=2&&(n2+i)<n; i++) {
        int a=n2-i;
        int b=n2+i;

        //然后求这ab是不是都是素数就行了
        int a_issusu=1;
        for(int j=2;j<=sqrt(a);j++) //找a是不是素数
        {
            if(a%j==0)
            {
                a_issusu=0;  //标记不是素数
                break;
            }
        }

        if (a_issusu==0) {
            continue;   //如果不是素数那么ab没用
        }

        //看看b是不是素数
        int b_issusu=1;
        for(int j=2;j<=sqrt(b);j++)
        {
            if(b%j==0)
            {
                b_issusu=0;  //标记不是素数
                break;
            }
        }

        if (b_issusu==0) {
            continue;  //如果不是素数那么ab没用
        }

        if(a+b==n) //如何相等表示找到了
        {
            printf("%d\n%d",a,b);
            break;
        }
    }
   
    return 0;
}
发表于 2025-10-03 16:00:57 回复(0)
C
牛客660136683号头像 牛客660136683号 
#include <stdio.h>
int is(int x) {
    int i;
    int sum = 0;
    if (x == 2)return 1;
    for (i = 2; i < x; i++) {
        if (x % i == 0)return 0;
    }
    return 1;
}
int main() {
    int a;
    scanf("%d", &a);
    int i;
    if (a % 2 == 0) {
        for (i = 0; ; i++) {
            if (is(a / 2 + i) == 1 && is(a / 2 - i) == 1) {
                printf("%d\n%d", a / 2 - i, a / 2 + i);
                return 0;
            }
        }
    } else {
        for (i = 0; ; i++) {
            if (is(a / 2 + 1 + i) == 1 && is(a / 2 - i) == 1) {
                printf("%d\n%d", a / 2 - i, a / 2 + i + 1);
                return 0;
            }
        }
    }
}
从中间往两头查找即可。如20先判断10-10是否为素数，再判断9-11，8-12以此类推
发表于 2025-08-21 20:13:47 回复(0)
C
小峰-sinx头像 小峰-sinx
#include <stdio.h>

int is_sushu(int n) {
  for (int i = 2; i <= n / 2; ++i) {

    if (n % i == 0) {
      return 0;
    }
  }
  return 1;
}
int main() {
  int a;
  int flag = 0;
  scanf("%d", &a);

  for (int i = a / 2; i >= 2; i--) {
    if (is_sushu(i) && is_sushu(a - i)) {
      printf("%d\n%d", i, a - i);
      break;
    }
  }

  return 0;
}

发表于 2024-08-21 17:51:16 回复(0)
C
唐凌Zero头像 唐凌Zero 
#include <stdio.h>

// 提前生成小于1000的质数表，可减少时间复杂度
#define list_size   168

int prime_list[list_size]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997};

int main()
{
    int x;
    scanf("%d",&x);
    int a=0,b=1000;
    for(int i=0;i<list_size;i++)
    {
        for(int j=i;j<list_size;j++)
        {
            int aa=prime_list[i];
            int bb=prime_list[j];
            if(aa+bb==x)
            {
                if(bb-aa<b-a)
                {
                    b=bb;
                    a=aa;
                }
            }
        }
    }
    printf("%d\n%d",a,b);
    return 0;
}

发表于 2024-08-13 20:19:03 回复(0)
C
VictorGao头像 VictorGao 
#include <stdio.h>
#include<math.h>
int zhishu(int x)
{
    int i;
    for(i=2;i<=sqrt(x);i++)
    {
        if(x%i==0)
        return 0;
    }
    return 1;
}

int main() {
    int a, i,j,flag,cha,i1,j1;
    scanf("%d",&a);
    cha=a;
    for(i=2;i<=a/2;i++)
    {
        for(j=2;j<a;j++)
        {
            if(zhishu(i) && zhishu(j) && (i+j)==a)
            {
                if(cha>(j-i))
                {
                    i1=i;
                    j1=j;
                    cha=j-i;
                }
            }
            
        }
    
    }
    printf("%d\n%d",i1,j1);

    return 0;
}

编辑于 2024-03-06 19:29:45 回复(0)
C
墨夜风名头像 墨夜风名 
#include <stdio.h>

int isStone(int value)
{
    for(int i=2;i<value;i++){
        if(value % i == 0){
            return -1;
        }
    }
    return 0;
}

int findStone(int *arr,int len, int value)
{
    for(int i=0;i<len;i++){
        if(value == arr[i]){
            return 0;
        }
    }
    return 1;
}

int main() {
    int n;
    int arr[1000];
    int len = 0;
    
    scanf("%d", &n);

    for(int i=2;i<n;i++){
        if(isStone(i) == 0){
            arr[len++] = i;
        }
    }

    int minA =0;
    int minB =0;
    unsigned int min = -1;

    for(int i=0;i<len;i++){
        int a = arr[i];
        int b = n - arr[i];

        if(findStone(arr, len, b) != 0){
            continue;
        }
        
        int temp = a > b?a-b:b-a;
        if(temp < min){
            minA = a;
            minB = b;
            min = temp;
        }
    }
    printf("%d\n", minA);
    printf("%d\n", minB);

    return 0;
}

编辑于 2024-03-01 10:35:02 回复(0)
C
牛客770548236号头像 牛客770548236号
#include <math.h>
#include <stdio.h>
//判断是不是素数
int isprime(int n)
{  
    if(n == 2)
        return 1;
    else if(n%2==0)
        return 0;
    else
    {
        for(int i=2; i*i<=n; i++)
        {
            if(n%i==0)
                return 0;
        }
    }
    return 1;
}

void math(int n)
{
    int i =2;
    int min =n;
    for(i=2;i<=(n/2);i++)
    {
        if(isprime(i)&&isprime(n-i))//判断两个数是不是都是素数    
        {
            if(min>((n-i)-i))//计算差值
                min =(n-i)-i;
        }
    }
    printf("%d\n%d",(n-min)/2,n-((n-min)/2) );//根据差值最小还原素数
}

int main()
{
    int n = 0;
    scanf("%d",&n);

    math(n);

    return 0;
}
发表于 2023-12-10 17:12:08 回复(0)
C
猪猪侠的飞天梦头像 猪猪侠的飞天梦 
#include <math.h>
#include <stdio.h>
# include "math.h"
int main() {
    int n, b[500] = {0}, j = 0; 
    scanf("%d",&n);
    for(int i = 1; i<n; i += 2){
        int bi = 1;
        for(int k = 2; k<=i/2; k++){
            if(i%k==0) bi = 0;
        }
        if(bi) b[j++] = i;
    }
    b[0] = 2;
    //printf("%d\n",j);                               //b中包含k个1000以内的素数
    int mi = 1000, max = 0, min = 1000;
    for(int i=0; i<j; i++){
        for(int k = i; k<j; k ++){
            if(b[i] + b[k]  == n){
                if(b[j]-b[k]<mi){
                    mi = b[k]-b[i];
                    max = b[k];
                    min = b[i];
                }
            }
        }
    }
    printf("%d\n%d",min,max);
    return 0;
}

发表于 2023-12-03 17:47:11 回复(0)
C
彭洋a头像 彭洋a
#include <stdio.h>

int isprime(int n)
{
    for(int i = 2;i*i<=n;i++)
    {
        if(n%i == 0)
        {
            return 0;
        }
    }
    return 1;
}

int main() {
    int a;
    while (scanf("%d", &a) != EOF) {
        int b = a/2;
        for(int i = 0;i<b;i++)
        {
            if(isprime(b-i)&&isprime(b+i))
            {
                printf("%d\n%d\n",b-i,b+i);
                break;
            }
        }
    }
    return 0;
}
发表于 2023-10-11 21:24:14 回复(0)
C
goForWork头像 goForWork
#include <stdio.h>

int main() {
    //无疑问两个素数必定是一个大于等于n/2,和小于等于n/2的素数
    int isSS(int m);
    int n;
    scanf("%d",&n);
    int miner=n/2,maxer=n/2;
    while (!isSS(maxer)) maxer++;
    while (!isSS(miner)) miner--;
    while (1) {
        if (n==maxer+miner) {
            printf("%d\n%d",miner,maxer);
            break;
        }else if (n>maxer+miner) {
            maxer++;
            while (!isSS(maxer)) maxer++;
        }else {
            miner--;
            while (!isSS(miner)) miner--;
        }
    }

}
int isSS(int m){
    for (int i=2; i<m; i++) {
        if (m%i==0) {
            return 0;//不是素数
        }
    }
    return 1;//是素数
}
发表于 2023-08-29 21:30:51 回复(0)
C
烦恼的火龙果头像 烦恼的火龙果 
#include <math.h>
#include <stdio.h>

int sushu[1000]={0},top=0,s_min,s_max;

void compute_sushu(int num){
    for(int i=2;i<num;i++){
        int flag=0;
        for(int k=2;k<i;k++){
            if(i%k==0){
                flag=1;
                break;
            }
        }
        if(flag==0){
            sushu[top]=i;
            top++;
        }
    }
}
void comp(int num){
    int min=1000;
    for(int i=0;i<top;i++){
        for(int k=i;k<top;k++){
            if((sushu[i]+sushu[k])==num){
                if(min>(sushu[k]-sushu[i])){
                    min=sushu[k]-sushu[i];
                    s_max=k;
                    s_min=i;
                }
            }
        }
    }
}

int main() {
    int num;
    
    scanf("%d",&num);
    compute_sushu(num);//计算得出一个素数表
    comp(num);//计算得到两个差值最小的素数在素数表的下标
    printf("%d\n%d",sushu[s_min],sushu[s_max]);
    return 0;
}

发表于 2023-04-16 17:00:31 回复(0)
C
Lee QL头像 Lee QL 
#include <stdio.h>
#include <math.h>

int zhishu(int num) {
    int i;
    if (num < 2) {                  //小于2非质数
        return  0;
    }
    for (i = 2; i <= sqrt(num); i++) {
        if (num % i == 0) {        //可被整除非质数
            return 0;
        }
    }
    return 1;                     //其余质数
}


int main() {
    int l, m, num, i;
    scanf("%d", &num);
    l = m = num / 2;
    for (i = 0; l - i >= 2; i++) {
        if (zhishu(l - i) && zhishu(m + i)) {
            printf("%d\n%d", l - i, m + i);
            break;
        }
    }
    return 0;
}

发表于 2023-04-12 19:58:47 回复(0)
C
忘忧萱头像 忘忧萱 
#include <stdio.h>

int main() {
    /**显然对于一个偶数来说，差值最小的素数对应该最靠近其中轴的数字n/2
    因此只需要从其中轴开始向上或者向下遍历，同时保证找到的两个数都是素数
    那么就找到了题目要求的素数对*/
    int n;
    scanf("%d",&n);
    //if (n == 4) printf("2\n2\n");
    for (int i = n / 2; i <= n; i++) {
        int maybe = i;
        int flag = 0;
        for (int j = 2; j * j <= maybe; j++) {
            if (maybe % j == 0) {
                flag = 1;
                break;
            }
        }
        if (flag == 0) {
            int flag2 = 0;
            for (int j = 2; j * j <= (n-maybe); j++) {
                if ((n-maybe) % j == 0) {
                    flag2 = 1;
                    break;
                }
            }
            if(flag2==0) {
                printf("%d\n%d\n",n-maybe,maybe);
                break;
            }
        }
    }
    return 0;
}
如上，从中轴开始遍历，最先找到的就是满足条件的。
发表于 2023-01-01 16:31:23 回复(1)
C
Hongky头像 Hongky
#include <stdio.h>
#include <math.h>

int main()
{
    int n;
    int a,b;
    scanf("%d",&n);
    int A=n-2,B=2;
    int i;
    for(int j=2;j<=n/2;j++){
      for(i=2;i<=sqrt(j);i++)        //查找素数a
        if(j%i==0)
          break;
      if(i>sqrt(j))
        a=j;            //找到a
      else
        continue;
     
      for(i=2;i<=sqrt(n-a);i++)             //查找素数b
        if((n-a)%i==0)
          break;
      if(i>sqrt(n-a))
        b=n-a;          //找到b
      else
        continue;

      if(abs(a-b)<abs(A-B))
        A=a;B=b;
    }
    printf("%d\n%d",A,B);

       return 0;
}

发表于 2022-07-19 23:15:26 回复(0)
C
好久不见，最近好吗头像 好久不见，最近好吗
//基本思路：
//取数中值,左右同步移动，判断两者同为素数就好
/*
            20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
                     i<--- ||   --->j
*/


#include <stdio.h>
#include <stdlib.h>

int is_primer(int n)
{
    int i = 0,flag = 0;
    for(i = 2; i < n; i++)
    {
        if(n%i == 0)
        {
            return 0;
        }       
    }  
    return 1;
}

int main(void)
{
    int n;
    scanf("%d",&n);
    
    int i = 0,j = 0;
    for(i = n/2,j = n/2;  i>1,j<n; i--,j++)
    {
        if(is_primer(i) && is_primer(j))
        {
            printf("%d\n",i);
            printf("%d\n",j);
            break;
        }
    }
    return 0;
}
发表于 2022-06-18 12:15:24 回复(0)
C
发家致富奔小康头像 发家致富奔小康
#include <stdio.h>
int flag(int n)
{
    int i,flag;
    if(n==1)
    {
        flag=0;
        
    }
    for(i=2;i<n;i++)
    {
        if(n%i==0)
        {
            flag=0;
            break;
        }
        
    }
    flag=1;
    return flag;
    
}



int main()
{
  int num,dif,min;
  int i,j,k;
  scanf("%d",&num);
   min=num; 
  for(i=1;i<=num/2;i++)
  {
      j=num-i;
      //i,j都是素数
      if(flag(i)==1 && flag(j)==1)
      {
        dif=j-i;
        if(dif<min)
        {
          min=dif;
          k=i;
        }
      }
  }
    printf("%d\n%d\n",k,num-k);
    
    return 0;
    
    
}
发表于 2022-06-08 20:20:00 回复(1)
C
baixu头像 baixu
#include<stdio.h>

int main() {
    int val;
    int num[1000];
    scanf("%d", &val);
    int i, j;
    int pre;
    int next;
    int max = 10000;
    int k = 0;
    //得到素数
    for (i = 1; i <= val; i++) { //1是素数从2开始
        int flg = 0;
        for (j = 2; j < i; j++) { //和2-本身-1取余有0则不为素数
            if ((i % j) == 0) {
                flg = 1; //不是素数
            }
        }
        if (flg == 0) {
            num[k++] = i;
            if (val == (i * 2)) {
                num[k++] = i;
            }
        }
    }
    //比较组合找到最小的素数之差
    for (int i = 1; i < k; i++) {
        for (int j = i + 1; j < k; j++) {
            if (num[i] + num[j] == val) {
                if ((num[j] - num[i]) < max) {
                    max = num[j] - num[i];
                    pre = num[i];
                    next = num[j];
                }
            }
        }
    }
    printf("%d\n", pre);
    printf("%d\n", next);
    return 0;
}
发表于 2022-04-05 10:54:10 回复(0)
C
viod头像 viod
简单题提交几次才过，第一次通过率42%，第二次81%，第三次100%。总结就是情况没有考虑全面，提交看到没通过的测试用例才恍然大悟，做题还是得想多一点才行。 
#include<stdio.h>

int isPnumber(int n){
    for(int i=2;i<n;i++){
        if(n%i==0) return 0;
        else if(i==n-1) return n;
    }return 0;  //for循环内是条件分支时需要在循环外加上return出口，返回值可以是任意值代表异常，否则编译器会警告，因为循环不可预测，需要正常出口和异常出口。
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        if(n==4) { printf("2\n2\n"); break; }  //特殊情况直接输出结果
        int mid=n/2;
        int low=0,high=0;
        for(int j=1;(low==0)||(high==0)||(low+high!=n);j++){
             if(isPnumber(mid-j)) low=mid-j;
             if(isPnumber(mid+j)) high=mid+j;
        }
        if(isPnumber(mid))
            printf("%d\n%d\n",mid,mid);   //偶数的中间数为刚好素数的情况

        else printf("%d\n%d\n",low,high);
    }
}
发表于 2022-03-31 04:30:01 回复(0)
C
牛客991584878号头像 牛客991584878号 
#include<stdio.h>
int main()
{
    int a=0;
    int i=0;
    while(scanf("%d",&a)!=EOF)
    {
       for(i=a/2;i>=2;i--)
        { 
    //       printf("%d",sushu(i));
        
            if(sushu(i)==0&&sushu(a-i)==0)
            {
               printf("%d\n",i);
               printf("%d\n",a-i);
                break ;
            }
        }
    }
}

int sushu(int i)
{
    int flag=0;              //flag=0,为素数，1为非素数
    int j=0;
    for(j=2;j<i;j++)
    {   
        if(i%j==0)
        {
            flag=1;
            break ;
        }
    }
    if(flag==0) return 0;
    else 
        return 1;
}

发表于 2021-11-16 23:24:06 回复(0)
C
致爱丽丝头像 致爱丽丝
先求得SIZE内的所有素数，再查表即可
查表从输入的偶数的半值开始向下查找，当两个值都是素数时即满足。 
#include <stdio.h>
#include <math.h>

#define SIZE 1000

int prime[SIZE+1];

void getprime(void);
void checknum(int num);

int main(void)
{
    int num;
    getprime();
    while(scanf("%d",&num)!=EOF){
        checknum(num);
    }
    return 0;
}

void getprime(void)
{
    int i,j,tmp,flag;
    prime[1] = 1,prime[2] = 1,prime[3] = 1;
    for(i=5; i<=SIZE; i+=2){        //偶数不是素数
        tmp = sqrtf(i);
        flag = 1;
        for(j = 3; j <= tmp; j+=2){    //被除数不是偶数
            if(i % j == 0) flag = 0;
        }
        if(flag) prime[i] = 1;
    }
}

void checknum(int num)
{
    int half,i,j;
    for(i = num/2;i>=1;i--){
        j = num - i;
        if(prime[i] && prime[j]){
            printf("%d\n%d\n",i,j);
            break;
        }
    }
}


发表于 2021-11-09 14:53:00 回复(0)
提交观点

问题信息

穷举 基础数学 查找
难度：
24条回答 37652浏览

热门推荐

通过挑战的用户

查看代码

相关试题

查找组成一个偶数最接近的两个素数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号