You are viewing a single comment's thread. Return to all 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; }
}
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #60: Prime pair sets
You are viewing a single comment's thread. Return to all 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 {
}