两个素数之和

下面是一个使用回溯来加速程序的解决方案。

public class PrimeSum {

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

  private static void findSolutions(int[] a, int n) {
    if(n >= a.length) {
      System.out.println(java.util.Arrays.toString(a));
    } else {
      for(int i = n; i < a.length; i++) {
        if(n == 0 || isPrime(a[n - 1] + a[i])) {
          int t = a[n];
          a[n] = a[i];
          a[i] = t;
          findSolutions(a, n + 1);
          t = a[n];
          a[n] = a[i];
          a[i] = t;
        }
      }
    }
  }

  public static void main(String[] args) {
    int[] a = new int[4];
    for(int i = 0; i < a.length; i++) {
      a[i] = i + 1;
    }
    findSolutions(a, 0);
  }
}

我采取了不同的方法。首先我看看哪些是允许的。因此,当您从数字4开始时,您有以下选项:

• 把2和1或3结合起来
• 把3和2或4结合起来

你现在需要做的是,从两个数字的潜在序列开始:

• 1,2
• 1,4
• 3,2
• 3,4
• 4,1

在那之后你就开始扩展它们。因此,在第一个(1,2)的情况下,您可以选择添加1或3,而对于2,可用的选项是1或3(请参阅第一个项目符号列表)。这就给出了序列1,2,1和1,2,3。由于不能两次使用数字,第一个选项可以忽略。

这样,您将得到以下三个数字的序列:

• 1,4,3
• 2,1,4
• 2,3,4
• 3,2,1
• 4,1,2

• 1,2,3,4
• 1,4,3,2
• 2,1,4,3
• 3,2,1,4
• 4,1,2,3
• 4,3,2,1

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;


public class Main2 {
    static Scanner sc = new Scanner(System.in);

    private static boolean isPrime(int number) {
        if(number % 2 == 0) {
            return false;
        }
        for(int i = 3; i * i <= number; i += 2) {
          if(number % i == 0) return false;
        }
        return true;
      }

    public static void main(String[] args) {

        //Get number from user
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter a value");
        int number = scanner.nextInt();

        LinkedList<LinkedList<Integer>> solutions = new LinkedList<>();

        //Make a HashMap with all the viable combinations using two numbers
        //Make a HashMap with all potential combinations
        HashMap<Integer, LinkedList<Integer>> viableCombinations = new HashMap<>();
        LinkedList<LinkedList<Integer>> potentialSolutions = new LinkedList<>();
        for (int i = 1; i <= number; i++) {
            for (int j = i + 1; j <= number; j++) {
                if (isPrime(i+j)) {
                    if (viableCombinations.containsKey(i)) {
                        viableCombinations.get(i).add(j);
                    }
                    else {
                        LinkedList<Integer> newCombination = new LinkedList<Integer>();
                        newCombination.add(j);
                        viableCombinations.put(i, newCombination);
                    }
                    if (viableCombinations.containsKey(j)) {
                        viableCombinations.get(j).add(i);
                    }
                    else {
                        LinkedList<Integer> newCombination = new LinkedList<Integer>();
                        newCombination.add(i);
                        viableCombinations.put(j, newCombination);
                    }

                    LinkedList<Integer> combination = new LinkedList<>();
                    combination.add(i);
                    combination.add(j);
                    potentialSolutions.add(combination);
                    combination = new LinkedList<>();
                    combination.add(j);
                    combination.add(i);
                    potentialSolutions.add(combination);
                }
            }
        }

        //Extend HashMap with all viable combinations
        while (potentialSolutions.size() > 0) {
            LinkedList<Integer> potentialSolution = potentialSolutions.pop();
            if (potentialSolution.size() == number) {
                solutions.add(potentialSolution);
            }
            else {
                LinkedList<Integer> combinations = viableCombinations.get(potentialSolution.getLast());
                for (int i = 0; i < combinations.size(); i++) {
                    LinkedList<Integer> newPotentialSolution = new LinkedList<>(potentialSolution);
                    if (!newPotentialSolution.contains(combinations.get(i))) {
                        newPotentialSolution.add(combinations.get(i));
                        potentialSolutions.add(newPotentialSolution);
                    }
                }
            }

        }
        System.out.println(solutions);
    }
}