首页 > 试题广场 >

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

[编程题]查找组成一个偶数最接近的两个素数
  • 热度指数：158582 时间限制：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
算法知识视频讲解
添加回答
Java
沉稳的猕猴桃准备进厂头像 沉稳的猕猴桃准备进厂 
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();

        for (int i = num/2; i >= 1 ; i--) {
            if(isTrue(i)&&isTrue(num-i)){
                System.out.println(i);
                System.out.println(num-i);
                return;
            }
        }
    }

    public static boolean isTrue(int n){
        if(n<=3)
            return true;
        if(n%2==0||n%3==0)
            return false;
        for (int i = 6; i <= n/2; i+=6) {
            if(n%(i-1)==0||n%(i+1)==0)
                return false;
        }
        return true;
    }
}

发表于 2025-02-10 17:52:26 回复(0)
Java
牛客248641941号头像 牛客248641941号
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        for (int i=num/2; i<num; i++){
            if (ifNumPrime(i) && ifNumPrime(num -i)){
                System.out.println(num - i);
                System.out.println(i);
                break;
            }
        }
    }

    private static boolean ifNumPrime(int n){
        if (n <= 1) {
            return false;
        }else if (n <= 3) {
            return true;
        }else if (n % 2 == 0 || n % 3 == 0) {
            return false;
        }
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}
发表于 2024-08-03 01:27:53 回复(0)
Java
牛客76365361号头像 牛客76365361号
构造到n的质数表，然后查表，这样可以起到缓存的效果。 
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        TreeSet<Integer> primes = build(t);
        int a;
        for(a = t/2; a>1; a--){
            if (primes.contains(a) && primes.contains(t-a)) {
                break;
            }
        }
        System.out.println(a);
        System.out.print(t-a);
    }

    static TreeSet<Integer> build(int n) {
        TreeSet<Integer> result = new TreeSet<>();
        result.add(2);
        bloop:
        for (int i = 3; i <= n; i++) {
            int to = (int) (Math.sqrt(i) + 0.5);
            for (int e : result) {
                if (e > to) {
                    break;
                }
                if (i % e == 0) {
                    continue bloop;
                }
            }
            result.add(i);
        }
        return result;
    }
}


发表于 2024-07-02 00:11:54 回复(0)
Java
Kili_66头像 Kili_66 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m1 = n / 2;
        int m2 = n / 2;
        while( !isPrime(m1) || !isPrime(m2)){
            m1--;
            m2++;
        }
        System.out.println(m1);
        System.out.println(m2);
    }

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

发表于 2023-11-25 21:07:18 回复(0)
Java
tiger137头像 tiger137
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) { // 注意 while 处理多个 case
            int n = getPrime(in.nextInt());
            System.out.println(i - n);
            System.out.println(n);
        }
    }

    public static int getPrime(int n) {
        for (int i = n / 2; i < n; i++) {
            if (isPrime(i) && isPrime(n - i)) {
                return i;
            }
        }
        return 0;
    }
    public static boolean isPrime(int n) {
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
}
发表于 2023-11-14 21:33:00 回复(0)
Java
牛客214364484号头像 牛客214364484号 
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()){ 
            int[] ary = new int[1000];
            int num = sc.nextInt();
            int count = 0;
            for(int i = 2;i < num;i++){    //1不算质数
                if(isPrime(i)){            //如果是质数，从0位置开始依次放进数组
                    ary[count] = i;
                    count++;
                }
            }
            int min = ary[count-1];
            int m = 0, n = 0;
            f1:for(int i = 0;i < count;i++){    //直接穷举,我之前是用1/2处开始一左一右寻找，但是示例118竟然两个都在右边，
                                                //与其这样一个一个面对奇怪的示例，不如直接穷举
                for(int j = 0;j < count;j++){ 
                    if((num == ary[i] + ary[j]) && (Math.abs(ary[i] - ary[j]) < min)){
                        m = ary[i];
                        n = ary[j];
                        min = Math.abs(ary[i] - ary[j]);
                    }
                }
            }
            System.out.println(m);
            System.out.println(n);
        }
        sc.close();
    }

    public static boolean isPrime(int num){  //判断是否为质数
        for(int i = 2;i < num;i++){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }
}

发表于 2023-10-18 15:48:12 回复(0)
Java
呜哈哈_头像 呜哈哈_ 
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        // 偶数
        if (num % 2 == 0) {
            int m = num / 2 ;
            int m1 = m;
            int m2 = m;
            while (isTrue(m1) || isTrue(m2)) {
                m1--;
                m2++;
            }
            System.out.println(m1);
            System.out.println(m2);
        }

    }
    private static boolean isTrue(int num) {
        boolean r = false;
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                r =  true;
                break;
            }
        }
        return r;
    }
}

发表于 2023-10-13 15:10:43 回复(0)
Java
牛客106397800号头像 牛客106397800号 
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        int number = Integer.parseInt(line);

        // 如果一个数的两个素数对差值最小，这两个数接近number/2，所以从number/2开始循环，找到就退出循环
        for (int i = number / 2; i > 1; i--) {
            if (isPrime(i) && isPrime((number - i))) {
                System.out.println(i);
                System.out.println(number - i);
                break;
            }
        }
    }

    /**
     * 判断一个数是否位素数
     *
     * @param number
     * @return
     */
    private static boolean isPrime(int number) {
        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (number % i == 0) {
                return false;
            }
        }

        return true;
    }
}

发表于 2023-08-11 08:47:43 回复(0)
Java
雨不休头像 雨不休 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        /*while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = in.nextInt();
            System.out.println(a + b);
        }*/
        int n = in.nextInt();
        int a = n/2;
        int b = n/2;
        while(a>=2 && b<n){
            if(prim(a) && prim(b)){
                System.out.println(a);
                System.out.println(b);
                break;
            }else{
                a--;
                b++;
            }
        }
    }
    public static boolean prim(int num){
        for(int i = 2 ; i<num ; i++){
            if(num%i == 0){
                return false;
            }
        }
        return true;
    }
}

发表于 2023-06-19 18:55:39 回复(0)
Java
一二三四五lhs头像 一二三四五lhs
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            funHJ60(a);
        }
    }
    public static void funHJ60(int num) {
        if (num % 2 == 1) {
            return;
        } else if (num == 4) {
            System.out.println(2);
            System.out.println(2);
            return;
        }
        int mid = num / 2;
        int left = 0;
        int right = 0;
        if (mid % 2 == 0) {
            left = mid - 1;
            right = mid + 1;
        }
        if (mid % 2 == 1) {
            left = mid;
            right = mid;
        }
        boolean b = true;
        int lid = 0;
        int rid = 0;
        while (b) {
            for (int i = 2; i <= left / 2; i++) {
                if (left % i == 0) {
                    left -= 2;
                    right += 2;
                    lid = 0;
                    break;
                }
                if (i == left / 2) {
                    lid = 1;
                    for (int j = 2; j <= right / 2; j++) {
                        if (right % j == 0) {
                            right += 2;
                            left -= 2;
                            break;
                        }
                        if (j == right / 2) {
                            rid = 1;
                            if (lid == 1 && rid == 1) {
                                b = false;
                            }
                        }
                    }
                }
            }
        }
        System.out.println(left);
        System.out.println(right);
    }
}
发表于 2023-06-18 13:28:39 回复(0)
Java
牛客604637229号头像 牛客604637229号
 public static boolean isZhi(int num){
        boolean flag = true;
        for(int i=2;i<=(int)Math.sqrt(num);i++){
            if(num%i==0){
                flag = false;
                break;
            }
        }
        return flag;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            for(int i=a/2;i>1;i--){
                if(isZhi(i) &&isZhi(a-i)){
                    System.out.println(i);
                    System.out.println(a-i);
                    break;
                }
            }

           
        }
    }
发表于 2023-04-22 18:50:56 回复(0)
Java
林深时er头像 林深时er 
import java.util.Scanner;

import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws Exception{
        //素数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        while((str=buf.readLine())!=null){
            int num=Integer.parseInt(str);
            int sub = Integer.MAX_VALUE; //保存两个质数之间的差值
            int[] res = new int[2];
            for(int i=2;i<=num/2;i++){
                if(isPrime(i)==true&&isPrime(num-i)==true){
                    if(num-2*i<sub) sub = num-2*i;
                    res[0] = i;
                    res[1] = num-i;
                }
            }
            System.out.println(res[0]);
            System.out.println(res[1]);
        }
    }
    public static boolean isPrime(int num){ //判断一个数是否为质数（素数）
        for(int i=2;i<=num/2;i++){
            if(num%i==0) return false;
        }
        return true;
    }
}

发表于 2023-04-09 13:52:53 回复(0)
Java
西伯利亚牧羊人头像 西伯利亚牧羊人 
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int b = a/2;
            for(int i = b; i > 0; i--) { //从中位数开始判断，减少循环次数
                if(check(i) && check(a-i)) {
                    System.out.println(i);
                    System.out.println(a-i);
                    break;
                }
            }
        }
    }
    public static boolean check(int num) {
        for(int i = 2; i <= Math.sqrt(num); i++) { 
            if(num % i == 0) {
                return false;
            }
        }
        return true;
    }
}
发表于 2023-04-03 17:06:02 回复(0)
Java
子安1112头像 子安1112
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int o = in.nextInt();
            int avg = o / 2;
            for(int i = 0; i < avg; i++){
                int f = avg - i;
                int s = avg + i;
                if(isSushu(f) && isSushu(s)){
                    System.out.println(f);
                    System.out.println(s);
                    break;
                }
            }
        }
    }

    private static boolean isSushu(int n){
        if(n < 0 ){
            return false;
        }
        if(n == 1 || n == 2){
            return true;
        }
        for(int i = 2; i * i <= n; i++){
            if(n % i == 0){
                return false;
            }
        }
        return true;
    }
}
发表于 2023-02-16 09:27:39 回复(0)
Java
Jeremy777头像 Jeremy777 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int sum = in.nextInt();
        for (int i = sum / 2; i < sum; i++) {
            if (isPrime(i) && isPrime(sum - i)) {
                System.out.println(sum - i);
                System.out.println(i);
                return;
            }
        }
    }
    public static Boolean isPrime(Integer x) {
        if (x < 2)
            return true;
        for (int i = 2; i <= Math.sqrt(x); i++) {
            if (x % i == 0)
                return false;
        }
        return true;
    }
}

发表于 2023-01-04 01:02:07 回复(0)
Java
bvb1头像 bvb1 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            int k = in.nextInt();
            int a = k/2;
            int b = k/2;
            while(a>0){
                if(isPrime(a)&&isPrime(b)){
                    break;
                }
                a--;
                b++;
            }
            System.out.println(a);
            System.out.println(b);
        }
        
    }
    public static boolean isPrime(int n){
        for(int i=2;i<n;i++){
            if(n%i==0){return false;}
        }
        return true;
    }
}


发表于 2022-11-10 03:49:14 回复(0)
Java
橘子拒绝内卷头像 橘子拒绝内卷 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static boolean isPrimeNum(int n){
        for(int i = 2;i <= Math.sqrt(n);i++){
            for(int j = 2;j <= n/2;j++){
                if(i * j == n){
                    return false;
                }
            }
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ret1 = n/2;
        int ret2 = n/2;
        while(!isPrimeNum(ret1) || !isPrimeNum(ret2)){
            while(!isPrimeNum(ret1)){
                ret1--;
            }
            while(!isPrimeNum(ret2)){
                ret2++;
            }
            if(ret1+ret2 > n){
                ret1--;
            }else if(ret1+ret2 < n){
                ret2++;
            }else{
                break;
            }
        }
        System.out.println(ret1);
        System.out.println(ret2);
    }
}
让两个数都从n/2的位置出发，一个向下递减找素数，一个向上递增找素数，当两个数都是素数的时候，判断它们的和是否等于n，如果它们的和大于n，就让向下递减的数继续向下递减找更小的素数；如果它们的和小于n，就让向上递增的数继续向上递增找更大的素数。
发表于 2022-11-05 14:00:46 回复(0)
Java
Sawyer_lILi头像 Sawyer_lILi
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sNum = 0;
        int gap = n/2;
        for(int i = 1;i<=n/2;i++){
            // if(!isPrime(i)){
            //     continue;
            // }
            if(isPrime(i)&&isPrime(n-i)){
                if(n/2-i<gap){
                sNum = i;
                gap = n/2-i;
                }
            }
        }    
        System.out.println(sNum);
        System.out.println(n-sNum);
    }

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

我是纱布，图书馆太吵，把质数和奇数搞混了，注释掉的是原本以为一个偶数一定是两个质数之和，其实是奇数之和（n>4）
发表于 2022-10-04 22:23:36 回复(0)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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