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;
}

}

here is the C# code using System; using System.Collections.Generic; using System.Linq;

class Program { // Cache for concatenated prime checks. static Dictionary primeCache = new Dictionary();

static void Main()
{
    // Read input: N and K separated by a space.
    string[] tokens = Console.ReadLine().Split();
    int N = int.Parse(tokens[0]);
    int K = int.Parse(tokens[1]);

    // Generate all primes less than N.
    List<int> primes = SievePrimes(N);
    int nprimes = primes.Count;

    // Precompute 10^(number of digits) for each prime.
    int[] pow10 = new int[nprimes];
    for (int i = 0; i < nprimes; i++)
    {
        int digits = primes[i].ToString().Length;
        pow10[i] = (int)Math.Pow(10, digits);
    }

    // Build compatibility lists: for each prime (index i), comp[i] holds indices j (with j > i)
    // such that both concatenations (primes[i] followed by primes[j] and vice-versa) are prime.
    List<int>[] comp = new List<int>[nprimes];
    for (int i = 0; i < nprimes; i++)
        comp[i] = new List<int>();

    for (int i = 0; i < nprimes; i++)
    {
        for (int j = i + 1; j < nprimes; j++)
        {
            int concat1 = primes[i] * pow10[j] + primes[j];
            int concat2 = primes[j] * pow10[i] + primes[i];
            if (IsConcatPrime(concat1) && IsConcatPrime(concat2))
                comp[i].Add(j);
        }
    }

    // Build HashSet versions for fast candidate intersection.
    HashSet<int>[] compHS = new HashSet<int>[nprimes];
    for (int i = 0; i < nprimes; i++)
        compHS[i] = new HashSet<int>(comp[i]);

    List<int> currentSet = new List<int>();
    List<int> sums = new List<int>();

    // Try each prime as a starting point.
    for (int i = 0; i < nprimes; i++)
    {
        currentSet.Add(i);
        List<int> candidates = new List<int>(comp[i]);
        Search(comp, compHS, primes, currentSet, candidates, K, sums);
        currentSet.RemoveAt(currentSet.Count - 1);
    }

    // Sort and print the resulting sums.
    sums.Sort();
    foreach (var s in sums)
        Console.WriteLine(s);
}

// Backtracking search for sets of K primes.
static void Search(List<int>[] comp, HashSet<int>[] compHS, List<int> primes,
                   List<int> currentSet, List<int> candidates, int K, List<int> sums)
{
    if (currentSet.Count == K)
    {
        int sum = 0;
        foreach (var idx in currentSet)
            sum += primes[idx];
        sums.Add(sum);
        return;
    }

    for (int i = 0; i < candidates.Count; i++)
    {
        int candidateIndex = candidates[i];
        List<int> newCandidates = new List<int>();
        // Only consider candidates later in the list to maintain increasing order.
        for (int j = i + 1; j < candidates.Count; j++)
        {
            int nextCandidate = candidates[j];
            if (compHS[candidateIndex].Contains(nextCandidate))
                newCandidates.Add(nextCandidate);
        }
        currentSet.Add(candidateIndex);
        Search(comp, compHS, primes, currentSet, newCandidates, K, sums);
        currentSet.RemoveAt(currentSet.Count - 1);
    }
}

// Sieve of Eratosthenes to get all primes less than N.
static List<int> SievePrimes(int N)
{
    bool[] isComposite = new bool[N];
    List<int> primes = new List<int>();
    for (int i = 2; i < N; i++)
    {
        if (!isComposite[i])
        {
            primes.Add(i);
            for (int j = i * 2; j < N; j += i)
                isComposite[j] = true;
        }
    }
    return primes;
}

// Cached check for concatenated primes.
static bool IsConcatPrime(int x)
{
    if (primeCache.ContainsKey(x))
        return primeCache[x];
    bool result = IsPrimeMR(x);
    primeCache[x] = result;
    return result;
}

// Deterministic Miller-Rabin for 32-bit numbers using bases 2, 7, and 61.
static bool IsPrimeMR(int n)
{
    if (n < 2) return false;
    if (n % 2 == 0) return n == 2;

    // Write n-1 as d * 2^s.
    int d = n - 1;
    int s = 0;
    while ((d & 1) == 0)
    {
        d /= 2;
        s++;
    }

    int[] bases = { 2, 7, 61 };
    foreach (int a in bases)
    {
        if (a % n == 0) continue;
        long x = ModPow(a, d, n);
        if (x == 1 || x == n - 1)
            continue;
        bool 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;
}

// Fast modular exponentiation.
static long ModPow(long a, long d, long mod)
{
    long result = 1;
    a %= mod;
    while (d > 0)
    {
        if ((d & 1) == 1)
            result = (result * a) % mod;
        a = (a * a) % mod;
        d >>= 1;
    }
    return result;
}

}

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 = 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);
    }
}

}

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);
        }
    }
}

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.