首页 > 试题广场 >

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

[编程题]查找组成一个偶数最接近的两个素数

热度指数：167910 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的偶数 $n$ ，找出两个素数 $a,b$ ，满足：
$\hspace{23pt}\bullet\,$ 它们的和等于 $n$ ；
$\hspace{23pt}\bullet\,$ 它们的差值的绝对值最小。

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

输入描述:

输入一个整数 。保证  是偶数。

输出描述:

第一行输出一个整数 ，代表满足条件的素数对中的较小者。
第二行输出一个整数 ，代表满足条件的素数对中的较大者。

示例1

输入

输出

7
13

示例2

输入

输出

2
2

算法知识视频讲解

Java

牛客294738644号

import java.util.Scanner;
public class Main{
public static void main(String[]args){
Scanner scan =new Scanner(System.in);
int num = scan.nextInt();
int min =0;
int max=0;
int ha =num/2;
for(int i=0;i<=ha;i++){
if(isSushu(ha-i)&&isSushu(ha+i)){
min= ha-i;
max =ha+i;
break;
}
}
scan.close();
System.out.println(min);
System.out.println(max);
}
public static boolean isSushu(int num){
if(num<=2&&num>0){
return true;
}
for(int i=2;i<num;i++){
if(num%i==0){
return false;
}
}
return true;
}
}

发表于 2022-06-10 00:00:43 回复(0)

Python 3

牛客村-村长

def su(num):  #判断该数是否为素数
    a = []
    for i in range(1,num+1):
        if num%i == 0:
            a.append(i)
    if len(a) == 2:
        return 1
    else:
        return -1

while True:
    try:
        n = int(input())
        a = []
        for i in range(2,n):   #从2开始，有序递增，产生的素数也是从小到大排列好的
            num = i
            if su(num) == 1: #该数为素数时
                a.append(i)  #所有素数放入列表a
        b = []
        for i in range(len(a)):
            if (n-a[i]) in a:  #筛选出两数只和为n的情况
                if a[i] > n//2: #去除后半段重复的数据
                    break
                b.append(a[i])  #满足条件的数据放入新的列表，因为数据为有序数据，最后一组则为最佳答案

        print(b[len(b)-1])
        print(n-b[len(b)-1])

    except:
        break

#常规方法，好理解些

发表于 2022-06-09 17:37:26 回复(0)

C++

小斜方二十合截半二十面体

#include<bits/stdc++.h>
using namespace std;
bool isPrime(int a){
    for(int i=2;i<=sqrt(a);i++)
        if(a%i==0)
            return false;
    return true;
}
int main(){
    int a;
    cin>>a;
    for(int i=a/2;i>=2;i--){
        if(isPrime(i)&&isPrime(a-i)){
            cout<<i<<endl<<a-i;
            return 0;
        }
    }
}

发表于 2022-03-29 08:30:28 回复(0)

C++

牛客7045420号

#include <iostream>
#include <string>
using namespace std;

int is_prime(int a)
{
if(a <= 0) return 0;
if(a ==1 || a==2) return 1;

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

int main()
{
int val, tmp;

while(cin>>val)
{
if(val%2 != 0 || val <= 2) return -1;
tmp = val/2;

for(int i = tmp; i>=1; --i)
{
if(is_prime(i) && is_prime(val-i))
{
cout<<i<<endl;
cout<<val-i<<endl;
break;
}
}

}

return 0;
}

发表于 2021-10-07 21:38:06 回复(0)

Java

Sushine

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;
        while ((s = br.readLine()) != null) {
            int n = Integer.parseInt(s);
            for (int i = n / 2; i >= 2; i--) {
                if (prime(i) && prime(n - i)) {
                    System.out.println(i);
                    System.out.println(n - i);
                    break;
                }
            }
        }
    }

    public static boolean prime(int n) {
        for (int i = 2; i < n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public String destCity(List<List<String>> paths) {
        return "";
    }
}

发表于 2021-10-01 12:38:27 回复(0)

Java

牛客150518786号

import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = "";
        while ((str = br.readLine()) != null) {
            int n = Integer.parseInt(str);
            for (int i = n / 2; i < n - 2; i++) {
                if (isPrime(i) && isPrime(n - i)) {
                    System.out.println(String.format("%d\n%d", n - i, i));
                    break;
                }
            }
        }
        br.close();
    }
    private static boolean isPrime(int n) {
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

发表于 2021-09-27 18:39:15 回复(0)

pein531

从中心开始向两边扩散，遇到符合题意的素数对马上退出循环即可保证素数对的差值是最小的。先初始化两个数small和big均为这个偶数target的一半，然后检查small和big是否是素数，只要有一个不是，small就自减1，big=target-small，直到满足两个数都是素数。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null) {
            int target = Integer.parseInt(line.trim());
            int small = target / 2;
            int big = target - small;
            boolean smallIsPrime = false, bigIsPrime = false;
            do{
                smallIsPrime = isPrime(small);
                if(!smallIsPrime) {
                    small --;
                    big = target - small;
                    continue;
                }
                big = target - small;
                bigIsPrime = isPrime(big);
                if(!bigIsPrime) {
                    small --;
                    big = target - small;
                }
            }while(small > 2 && !(smallIsPrime && bigIsPrime));
            System.out.println(small);
            System.out.println(big);
        }
    }
    
    private static boolean isPrime(int num) {
        for(int factor = 2; factor <= (int)Math.sqrt(num) + 1; factor++)
            if(num % factor == 0) return false;
        return true;
    }
}

编辑于 2021-04-01 09:56:18 回复(0)

forecastorm

def is_prime(num):
    for i in range(2,num-1):
        if num%i ==0:
            return False
    return True
while True:
    try:
        num = int(input())
        left, right = num//2, num//2
        while left>=2 and right<=num-1:
            if left + right > num:
                left -=1
            elif left + right < num:
                right +=1
            else:
                if not is_prime(left):
                    left-=1
                    continue
                if not is_prime(right):
                    right+=1
                    continue
                print(left)
                print(right)
                break
    except Exception as e:
        break

从中间开始判断使得差值最小（可以是相同两个数），其后使用左右两个指针遍历，

如果两个数之后小于目标值，移动右指针

如果两个数之后大于目标值，移动左指针

如果左面的数不是质数，移动左指针

如果右面的数不是质数，移动右指针

编辑于 2021-01-01 05:08:24 回复(0)

Python

JeremyStar

def check_prime(num):
    for i in range(2, int(num**1/2)+1):
        if num % i == 0:
            return False
    return True


while True:
    try:
        even = int(input().strip())
        half = even // 2
        start = 0 if half % 2 == 1 else 1
        for i in range(start, half, 2):
            a, b = half + i, half - i
            if check_prime(a) and check_prime(b):
                print(b)
                print(a)
                break
    except:
        break

（1）选择从中间数开始，一加一减，保证和是输入数的同时，还达到了两个素数差值最小。（2）从奇数中寻找素数，每次跨度为2.

编辑于 2020-12-15 12:19:57 回复(0)

楚地夏忙

#include<bits/stdc++.h>
using namespace std;
bool is_su(int m)
{
    bool flag=1;
    for(int i=2;i*i<=m;i++)
    {
        if(m%i==0)
        {
            flag=0;
        }
    }
    return flag;
}
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=n/2;i>=1;i--)
        {
            if(is_su(i)==1)
            {
                if(is_su(n-i)==1)
                {
                    cout<<i<<endl;
                    cout<<n-i<<endl;
                    break;
                }
            }
        }
    }
    return 0;
}

发表于 2020-11-26 23:15:07 回复(0)

Discriminate

这道题用C写就很简单了，首先要清楚怎么算差值最小，两个数越接近差值就越小喽，既然输入是偶数，那就两个数初始值一半一半喽，谁不是素数那就一个加加，一个减减。最终的值一定差值最小。

#include "string.h"
#include <stdio.h>

int  sushuo(int a) /*判断一个数是不是素数，是的话返回1，不是返回0*/
{
    int i=2;
    for (i=2;i<a;i++)
    {
        if (a%i==0) return 0;

    }
    return 1;

}

int main (void)
{
    int input;
    while (scanf("%d",&input)!=EOF)
    {
    int a=0,b=0;
    a=b=input/2;
    int i;
    int j;
    
    for (i=0;i<input/2;i++)
    {
    if (sushuo(a)==0 || sushuo(b)==0)
    {
        a++;
        b--;
        
    }
    }

    printf("%d\r\n",b);
    printf("%d\r\n",a);        
    }

}

发表于 2020-08-23 19:21:55 回复(2)

Python

君临天下201804050931706

import math
def isPrime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            return False
    return True

while True:
    try:
        n = int(input())
        minP = 0
        maxP = n
        for i in range(2,int(n/2)+1):
            if isPrime(i) and isPrime(n-i) and (n-i-i)<(maxP-minP):
                minP = i
                maxP = n-i

        print(minP)
        print(maxP)

    except:
        break

发表于 2020-07-14 09:21:24 回复(0)

only_boy

#include <iostream>
#include <cmath>

using namespace std;
//一个从头出发，一个从尾巴出发，判断两数是否为素数，若是，则记录下来
//头的数不能大于尾巴的数 作为出口
//输出最终记录的值
bool isnum(int n)
{
	bool flag = true;
	for(int i = 2;i<=sqrt(n);i++)
	{
		if(n%i == 0)
		{
			flag = false;
		}
	}
	return flag;
}

int main()
{
    int n;
    while(cin >> n)
    {
        int a = 0,b=0;
        for(int i =1 ;i<=n;i++)
        {
            if(isnum(i) && isnum(n-i) && (i<=(n-i)))
            {
                a = i;
                b = n-i;
            }
        }
        cout<<a<<endl<<b<<endl;
    }
    return 0;
}

编辑于 2020-07-10 16:27:32 回复(0)

C/C++

WZ_Dale

本题首先需要判断素数，素数表示除过1和本身，不能被其它数整除。通过循环遍历来判断一个数是否为素数。最近的两个素数应该从最中间的位置开始向两边查找。

#include <iostream>
#include <algorithm>

using namespace std;
// 判断素数
bool isPrime(int a){
    int tmp = sqrt(a);
	
		    //只遍历到开方出，不能被开方左边的数整除，则一定不能被开方右边的数整除
	
    for(int i = 2; i <= tmp; ++i){
        if(a % i == 0){
            return false;
        }
    }
    return true;
}
int main(){
    int n;
    while(cin >> n){
        int i = n / 2;
                // 从中间向两边找
        for(; i > 0; --i){
            if(isPrime(i) && isPrime(n - i)){
                break;
            }
        }
        cout << i << endl << n - i << endl;
    }
    return 0;
}

发表于 2020-06-08 10:16:01 回复(0)

星辰大海sd

/**
 * 思路：由于差值最小的素数对 肯定是最靠近这个数的中位数，
 *  所以从中位数开始，依次判断是否是素数对，是的话直接输出即可
 */
import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            minSushuDui(scanner.nextInt());
        }
    }

    /**
     * 找出差值最小的素数对
     * @return
     */
    public static void minSushuDui(int n) {
        for (int i = n / 2; i < n; i++) {
            if (isSushu(i) && isSushu(n-i)){
                System.out.println(n-i);
                System.out.println(i);
                break;
            }
        }
    }

    /**
     * 判断一个数是否为素数:
     *  从2开始遍历i++，到数字本身大小之前停止，每次遍历判断这个数字能否被i整除。
     *  如果能被i整除，即num%i==0，则不是质数，返回false，否则返回true。
     */
    public static boolean isSushu(int num) {
        for (int i = 2; i < num; i++) {
            if (num%i==0){
                return false;
            }
        }
        return true;
    }
}

发表于 2020-04-22 10:03:44 回复(0)

南少201911241210480

#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i=n/2;i>0;i--)
        {
            int j=2;
            for(;j<i/2;j++)//判断i是不是质数
            {
                if(i%j==0)
                    break;
            }
            if(i/2==j)//当i是质数判断n-i是不是
            {
                int b=n-i;j=2;
                for(;j<b/2;j++)
                 {
                  if(b%j==0)
                    break;
                 }
            }
            if((n-i)/2==j)//两个都是质数
            {
                cout<<i<<endl<<n-i<<endl;
                break;
            }
        }
    }
    return 0;
}

发表于 2020-03-28 11:03:46 回复(0)

一直爬的蜗牛

while True:
    try:
        even = int(input())
        result = []
        res = []
        for i in range(2,even):
            for j in range(2,i):
                if i % j == 0:
                    break
            else:
                result.append(i)      

        for i in result:
            for j in result[::-1]:
                if i + j == even:
                    if abs(j-i) not in res:
                        res.append(abs(j-i))
        res.sort()      

        for i in result:
            for j in result[::-1]:
                if i + j == even and j - i == res[0]:
                    print(i)
                    print(j)
    except:
        break

1、算出#2到n之间所有的素数

2、两个符合条件的素数的距离放到列表res，并排序

3、将距离最小的两个素数找出来

发表于 2020-03-28 00:51:42 回复(0)

Python

朝夕_

while True:
  try:
    a,b,c = int(input()),[],[]
    for i in range(int(a/2),a):
      for j in range(2,int(i/2)+1):
        if i%j == 0:
          break
        elif j == int(i/2):
          b.append(i)
    for i in b:
      for j in range(2,int((a-i)/2)+1):
        if (a-i)%j == 0:
          break
        elif j == int((a-i)/2):
          c.append(i)
    print(a-c[0])
    print(c[0])
  except:
    break

发表于 2020-02-20 16:57:10 回复(0)

Panacea丶

import math


def is_prime(n):
    if n == 2:
        return True
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True


while True:
    try:
        n = eval(input())
        #从中间开始判断
        a = n // 2
        b = n - a
        while not is_prime(a)&nbs***bsp;not is_prime(b):
            a -= 1
            b += 1
        if a >= b:
            print("{}\n{}".format(b, a))
        else:
            print("{}\n{}".format(a, b))
    except:
        break

发表于 2020-02-04 16:53:40 回复(0)

iostream

从 num/2 处开始查找最小的质数max，并同时判断 min=num-min是否是质数

#include<iostream>
#include<algorithm>
using namespace std;
bool solution(int num) {
	for (int i = 2; i<=sqrt(num); i++) {
		if (num%i == 0)return false;
	}
	return true;
}

int main()
{
	int num;
	while (cin >> num) {
		int max = 0;
		int min = 0;
		for (int i = num/2; i<num; i++) {
			if (solution(i)&&solution(num-i)) {
				max= i;	
				min = num - i;
					break;
			}
		}
		cout << min << endl;
		cout << max << endl;
	}
	return 0;
}

发表于 2019-08-28 10:54:53 回复(0)