Project Euler #60: Prime pair sets

Sort by

recency

|

17 Discussions

|

  • + 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);
            }
        }
    }
    
  • + 0 comments

    This one is very complex; in Python had to end up doing lots of optimizations. Miller-Rabin can be made deterministic beneath a certain range, it is recommended to avoid the overhead of constant random. And clique hunting is easy with set operators if you have access to them. But you have to really squeeze every ounce of efficiency from every function; there are plenty of places to prune in the clique algorithms.

    I didn't end up needing multiprocessing that xperroni mentions, I didn't like the idea of processing power being the key to algorithmic optimizations for Project Euler.

  • + 0 comments

    After working on it for days, I was finally able to pass all tests using a solution written in Python 3. My tips, in spoiler order:

    Skip 2 and 5 in your prime sequence, since they will never be in any valid pairs.

    Use a fast prime sieve (for example this one) to generate all primes in the range first, then look for connections.

    As Ki Chun TONG suggested, use the generated prime list (or rather a set, for faster search times) as the first level in your prime checker, and Miller-Rabin as the second level if the number is not found there.

    Divide the generated primes into two sets primes_1 = {3} | {p for p in primes if p % 3 == 1} and primes_2 = {3} | {p for p in primes if p % 3 == 2}, then process them separately — the reason this can be done is that if p1 % 3 == 1 and p2 % 3 == 2 or vice versa, then the concatenation of p1 and p2 will be divisible by 3, and therefore (p1, p2) is not a valid pair.

    Use multiprocessing to process both of the above lists simultaneously.

  • + 0 comments

    Solved in Python 3, time limit exceeded
    Solved in Javascript, memory exceeded
    Solved in javascript generating primes upto 999999 and then checking primes upto sqrt(n) in isprime() , testcase 14 failed.
    What to do?
    Edit: My bad, I forgot to replace "br" tag with "\n" for K=5
    Same logic failed 3 test cases it python due to TLE and Javascript passed really fast. Weird

  • + 0 comments

    can someone help me with test case #14