Project Euler #60: Prime pair sets

  • + 0 comments

    Use Java 7 for this code

    import java.io.; import java.util.; import java.text.; import java.math.; import java.util.regex.*;

    public class Solution {

    private static HashMap<Long, Boolean> primeCache = new HashMap<>();
    
    private static boolean[] isCompositeSieve;
    
    private static ArrayList<Integer> primesList;
    
    private static final int MAX_PRIME_TO_CONSIDER_IN_SET = 100000; 
    
    private static int sieveLimit;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] tokens = br.readLine().split(" ");
        int N = Integer.parseInt(tokens[0]);
        int K = Integer.parseInt(tokens[1]);
    
        sieveLimit = Math.max(N, MAX_PRIME_TO_CONSIDER_IN_SET + 1000); 
        sievePrimes(N); 
        int nprimes = primesList.size();
    
        long[] pow10 = new long[nprimes];
        for (int i = 0; i < nprimes; i++) {
            int p = primesList.get(i);
            long currentPower = 1;
            int tempP = p;
            if (tempP == 0) { 
                currentPower = 10;
            } else {
                while (tempP > 0) {
                    currentPower *= 10;
                    tempP /= 10;
                }
            }
            pow10[i] = currentPower;
        }
    
        ArrayList<Integer>[] comp = new ArrayList[nprimes];
        for (int i = 0; i < nprimes; i++) {
            comp[i] = new ArrayList<>();
        }
    
        HashSet<Integer>[] compHS = new HashSet[nprimes];
        for (int i = 0; i < nprimes; i++) {
            compHS[i] = new HashSet<>();
        }
    
        for (int i = 0; i < nprimes; i++) {
            for (int j = i + 1; j < nprimes; j++) {
                long concat1 = (long)primesList.get(i) * pow10[j] + primesList.get(j);
                long concat2 = (long)primesList.get(j) * pow10[i] + primesList.get(i);
    
                if (isConcatPrime(concat1) && isConcatPrime(concat2)) {
                    comp[i].add(j);
                    compHS[i].add(j); 
                }
            }
        }
    
        ArrayList<Integer> currentSet = new ArrayList<>();
        ArrayList<Long> sums = new ArrayList<>();
        for (int i = 0; i < nprimes; i++) {
            if (nprimes - i < K) {
                break;
            }
    
            currentSet.add(i);
    
            ArrayList<Integer> candidates = new ArrayList<>(comp[i]);
            Search(comp, compHS, primesList, currentSet, candidates, K, sums);
            currentSet.remove(currentSet.size() - 1); 
        }
    
        Collections.sort(sums);
        for (long s : sums) {
            System.out.println(s);
        }
    }
    
    static void Search(ArrayList<Integer>[] comp, HashSet<Integer>[] compHS, ArrayList<Integer> primes,
                       ArrayList<Integer> currentSet, ArrayList<Integer> candidates, int K, ArrayList<Long> sums) {
        if (currentSet.size() == K) {
            long sum = 0;
            for (int idx : currentSet) {
                sum += primes.get(idx);
            }
            sums.add(sum);
            return;
        }
    
        if (candidates.size() < K - currentSet.size()) {
            return;
        }
    
        for (int i = 0; i < candidates.size(); i++) {
            int candidateIndex = candidates.get(i);
    
            ArrayList<Integer> newCandidates = new ArrayList<>();
            for (int j = i + 1; j < candidates.size(); j++) {
                int nextCandidate = candidates.get(j);
                if (compHS[candidateIndex].contains(nextCandidate)) {
                    newCandidates.add(nextCandidate);
                }
            }
    
            if (newCandidates.size() < K - (currentSet.size() + 1)) {
                continue; 
            }
    
            currentSet.add(candidateIndex);
            Search(comp, compHS, primes, currentSet, newCandidates, K, sums);
            currentSet.remove(currentSet.size() - 1); 
        }
    }
    
    static void sievePrimes(int N) {
        isCompositeSieve = new boolean[sieveLimit + 1];
        Arrays.fill(isCompositeSieve, false); 
        isCompositeSieve[0] = isCompositeSieve[1] = true;
    
        for (int i = 2; i * i <= sieveLimit; i++) { 
            if (!isCompositeSieve[i]) {
                for (long j = (long)i * i; j <= sieveLimit; j += i) { 
                    isCompositeSieve[(int)j] = true;
                }
            }
        }
    
        primesList = new ArrayList<>(); 
        for (int i = 2; i <= N; i++) { 
            if (!isCompositeSieve[i]) {
                if (i <= MAX_PRIME_TO_CONSIDER_IN_SET && i != 2 && i != 5) { 
                    primesList.add(i);
                }
            }
        }
    }
    
    static boolean isConcatPrime(long x) {
        if (primeCache.containsKey(x)) {
            return primeCache.get(x);
        }
    
        boolean result;
        if (x < isCompositeSieve.length && x >= 0) { 
            result = !isCompositeSieve[(int)x];
        } else { 
            result = isPrimeMR(x);
        }
    
        primeCache.put(x, result);
        return result;
    }
    
    private static final long[] MILLER_BASES = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 }; 
    
    static boolean isPrimeMR(long n) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
    
        long d = n - 1;
        int s = 0;
        while ((d & 1) == 0) {
            d >>= 1; // d /= 2
            s++;
        }
    
        for (long a : MILLER_BASES) {
            if (a >= n) continue;
    
            long x = modPow(a, d, n);
            if (x == 1 || x == n - 1) {
                continue;
            }
            boolean composite = true;
            for (int r = 1; r < s; r++) {
                x = (x * x) % n;
                if (x == n - 1) {
                    composite = false;
                    break;
                }
            }
            if (composite) {
                return false;
            }
        }
        return true;
    }
    
    static long modPow(long baseVal, long exp, long mod) {
        long res = 1;
        baseVal %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) { 
                res = (res * baseVal) % mod;
            }
            baseVal = (baseVal * baseVal) % mod;
            exp >>= 1; // exp /= 2
        }
        return res;
    }
    

    }