We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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);
}
}
}
Cookie support is required to access HackerRank
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 →
import java.io.; import java.util.;
public class Solution {
}