Выразить любое нечетное число больше 5 как сумму 3 простых

Question

Для данного нечетного числа n Я хочу эффективно вычислить 3 простые числа, сумма которых равна n, Если есть несколько решений, то я хочу одно с наименьшими простыми числами (я хочу 2+2+17=21 вместо 3+5+13=21)

Это всегда возможно дляn>5,

Мой нынешний подход состоит в том, чтобы уменьшить проблему до вычислений 2 простые числа, сумма которых равна n-3 а потом я просто вывести 2 вычисленные простые числа и 3 так как они, очевидно, в сумме составляют n, я выбираю 3 так как это наименьшее нечетное простое число, и когда я вычесть его из n Я получаю четное число, поэтому оно должно быть частью каждого решения, которое я ищу. Я использую это, чтобы вычислить сумму 2 простых чисел, это работает, если n четное, что это в моем случае (так как я вычел 3 из странного n).

Мой подход не работает, так как есть решения без 3 как слагаемое (41=2+2+37).

Есть ли простой подход, который я пропускаю?

Answer 1

Сначала проверьте, является ли n-4 простым. Если так, ваш ответ: {2, 2, n-4}. В противном случае ваш оригинальный подход будет работать. Вы никогда не будете использовать только один 2, потому что ваша сумма будет четной.

Answer 2

Вы можете попробовать что-то вроде этого:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * This class to find the Goldbach's Weak Conjecture
 */
public class OddGoldbachConjecture {

    //Recursively checks the divisors
    public static boolean isPrime(int number, int counter){
        if(counter>2){return false;}
        if(number!=1){counter++;}
        if(number%2==0){isPrime(number/2, counter);}
        else if(number%3==0){isPrime(number/3, counter);}
        else if(number%5==0){isPrime(number/5, counter);}
        else if(number%7==0){isPrime(number/7, counter);}
        else if(number%10==0){isPrime(number/10, counter);}
        return true;
    }


    //returns a list of the lowest 3 primes
    public static List<Integer> findOddGoldbachConj(List<Integer> factors, int number){

        Collections.reverse(factors); // sort in ascending order
        List<Integer> oddGoldbach = new ArrayList<>(); // to collect the result

        // find first if there is one or two primes that equals the number
        // after repeating one of them
        for(int i=0; i<factors.size(); i++){
            int factor = factors.get(i);
            if(factor*3 == number){
                oddGoldbach.addAll(Arrays.asList(factor, factor, factor));
                return oddGoldbach;
            }
            else if(factors.contains(number-(factor*2))){
                oddGoldbach.addAll(Arrays.asList(factor, factor,number-(factor*2)));
                return oddGoldbach;
            }
        }

        // the hard way and last option, finding 3 different primes 
        for(int i=0; i<factors.size(); i++){
            int factor = factors.get(i);
            for(int j=i+1; j<factors.size(); j++){
                int other = factors.get(j);
                for(int k=j+1; k<factors.size(); k++){
                    int other1 = factors.get(k);
                    if(factor+other+other1==number){
                       oddGoldbach.addAll(Arrays.asList(factor, other, other1));
                       return oddGoldbach;
                    }           
                }
            }
        }

        return null;
    }



   // test
    public static void main(String[] args) {
        // to contain intermediate produced numbers
        List<Integer> container = new ArrayList<>();
        int number = 0;
        System.out.println("Enter the number: ");
        Scanner scanner = new Scanner(System.in);
        try{number = Integer.parseInt(scanner.nextLine());}
        catch(NumberFormatException e){ 
            System.out.println("Invalid Input!"); 
            System.exit(0);
        }

        if(number>0){
           // find all the primes between 2 and number
           for(int i=number; i>=2; i--){if(isPrime(i,0)){container.add(i);}}

            System.out.println(findOddGoldbachConj(container, number));         
        }

        scanner.close();
    }
}

Тестовое задание

21      ->  [2, 2, 17]
41      ->  [2, 2, 37]
100     ->  [2, 19, 79]
5555    ->  [3, 3, 5549]
12345   ->  [7, 7, 12331]
1000000 ->  [2, 2, 999996]
1234567 ->  [2, 2, 1234563]