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
An unexpected error occurred. Please try reloading the page. If problem persists, please contact support@hackerrank.com
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 {
}