Project Euler #60: Prime pair sets

  • + 0 comments

    import java.io.; import java.util.;

    public class Solution {

    private static List<Long> sums = new ArrayList<>();
    
    // Merge two numbers, "append their digits"
    private static long merge(long a, long b) {
        long shift = 1;
        while (shift <= b) {
            shift *= 10;
        }
        return a * shift + b;
    }
    
    // Check if a number is prime
    private static boolean isPrime(long p) {
        if (p < 2) return false;
        if (p == 2 || p == 3) return true;
        if (p % 2 == 0 || p % 3 == 0) return false;
    
        for (long i = 5; i * i <= p; i += 6) {
            if (p % i == 0 || p % (i + 2) == 0) return false;
        }
        return true;
    }
    
    // Check if two numbers can be merged and the result is still prime
    private static boolean match(long a, long b) {
        return isPrime(merge(a, b)) && isPrime(merge(b, a));
    }
    
    // Find sets of primes of the specified size
    private static void findSets(int size, List<Integer> primes) {
        for (int i = 0; i < primes.size(); i++) {
            int smallPrime = primes.get(i);
            if (smallPrime == 5) continue;
    
            List<Integer> candidates = new ArrayList<>();
            for (int j = i + 1; j < primes.size(); j++) {
                int largePrime = primes.get(j);
                if (match(smallPrime, largePrime)) {
                    candidates.add(largePrime);
                }
            }
    
            if (size == 3) {
                checkTriple(smallPrime, candidates);
            } else if (size == 4) {
                checkQuadruple(smallPrime, candidates);
            } else if (size == 5) {
                checkQuintuple(smallPrime, candidates);
            }
        }
    }
    
    // Find and add sums for triplets
    private static void checkTriple(int first, List<Integer> candidates) {
        for (int i = 0; i < candidates.size(); i++) {
            for (int j = i + 1; j < candidates.size(); j++) {
                if (match(candidates.get(i), candidates.get(j))) {
                    sums.add((long) first + candidates.get(i) + candidates.get(j));
                }
            }
        }
    }
    
    // Find and add sums for quadruplets
    private static void checkQuadruple(int first, List<Integer> candidates) {
        for (int i = 0; i < candidates.size(); i++) {
            for (int j = i + 1; j < candidates.size(); j++) {
                if (!match(candidates.get(i), candidates.get(j))) continue;
    
                for (int k = j + 1; k < candidates.size(); k++) {
                    if (match(candidates.get(i), candidates.get(k)) && match(candidates.get(j), candidates.get(k))) {
                        sums.add((long) first + candidates.get(i) + candidates.get(j) + candidates.get(k));
                    }
                }
            }
        }
    }
    
    // Find and add sums for quintuplets
    private static void checkQuintuple(int first, List<Integer> candidates) {
        for (int i = 0; i < candidates.size(); i++) {
            for (int j = i + 1; j < candidates.size(); j++) {
                if (!match(candidates.get(i), candidates.get(j))) continue;
    
                for (int k = j + 1; k < candidates.size(); k++) {
                    if (!match(candidates.get(i), candidates.get(k)) || !match(candidates.get(j), candidates.get(k))) {
                        continue;
                    }
    
                    for (int l = k + 1; l < candidates.size(); l++) {
                        if (match(candidates.get(i), candidates.get(l)) && match(candidates.get(j), candidates.get(l))
                                && match(candidates.get(k), candidates.get(l))) {
                            sums.add((long) first + candidates.get(i) + candidates.get(j) + candidates.get(k)
                                    + candidates.get(l));
                        }
                    }
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int maxPrime = scanner.nextInt();
        int size = scanner.nextInt();
        scanner.close();
    
        List<Integer> primes = new ArrayList<>();
        primes.add(2); // Add 2 explicitly
    
        // Generate prime numbers using the Sieve of Eratosthenes
        boolean[] isPrime = new boolean[maxPrime + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
    
        for (int i = 2; i * i <= maxPrime; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= maxPrime; j += i) {
                    isPrime[j] = false;
                }
            }
        }
    
        for (int i = 3; i < maxPrime; i += 2) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
    
        findSets(size, primes);
    
        // Sort and print the sums
        Collections.sort(sums);
        for (long sum : sums) {
            System.out.println(sum);
        }
    }
    

    }