Sum of 2 numbers being prime

Question

I am working on a program where given a number say 4, I need to find out the possible ways to use all the numbers from 1 to 4, in such a way that the numbers next to each other sum to a prime number.

For example, if given number is 4, then possible ways are:

1 2 3 4
1 4 3 2

I am using the below approach, please let me know if there is any simplified approach:

Step 1: Find all prossible combinations of numbers 1 to 4, say

1 2 3 4
1 3 2 4
1 3 4 2
2 3 4 1
2 3 1 4
etc

Step 2: Find out what series matches the given requirement, and increment a counter. Finally display the value of counter.

Is there a better approach to this?

Answer 1

I took a somewhat different approach. First I look at which pairs are allowed. So, when you start with the number 4, you have the following options:

• combine 1 with 2 or 4
• combine 2 with 1 or 3
• combine 3 with 2 or 4
• combine 4 with 1 or 3

What you need to do now is, to start with the potential sequences of two numbers:

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

After that you just start to extent them. So in the case of the first (1,2), you have the option to add a 1 or a 3, as for 2 the available options are 1 or 3 (see first bullet-list). That gives the sequences 1,2,1 and 1,2,3. As you can't use numbers twice, the first option can be ignored.

That way, you end up with the following sequences of three numbers:

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

Continue doing this and you end up with the solution:

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

Here is my solution in code:

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);
    }
}

Answer 2

Here is a solution that uses backtracking to speed up the program.

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);
  }
}