Project Euler #60: Prime pair sets

  • + 0 comments

    JAva code

    4, 9, 14 cash are not work

    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 = 10;
            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 < 4)
                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 in any way and the result is still prime
        private static boolean match(long a, long b) {
            return isPrime(merge(a, b)) && isPrime(merge(b, a));
        }
    
        // Find all sets of primes with the specified size
        private static void findSets(int size, List<Integer> primes) {
            int maxPrime = Collections.max(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 since it's not generated
    
            // Find all primes up to the specified maxPrime
            for (int i = 3; i < maxPrime; i += 2) {
                boolean isPrime = true;
                for (int p : primes) {
                    if (p * p > i) {
                        break;
                    }
                    if (i % p == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime) {
                    primes.add(i);
                }
            }
    
            findSets(size, primes);
    
            // Sort and print the sums
            Collections.sort(sums);
            for (long sum : sums) {
                System.out.println(sum);
            }
        }
    }