You are viewing a single comment's thread. Return to all comments →
JAva code
import java.io.*; import java.util.*; public class Solution { static int N = 7; static int K = 3; static int L = 7; static Map<String, List<Integer>> M = new HashMap<>(); static int smPrime = 99999999; static void match(int num, StringBuilder regex, int dig, int howOften, int startPos) { char asDig = (char) (dig + '0'); for (int i = startPos; i < N; i++) { if (regex.charAt(i) != asDig) { continue; } if (i == 0 && asDig == '0') { continue; } regex.setCharAt(i, '.'); if (howOften == 1) { List<Integer> addTo = M.computeIfAbsent(regex.toString(), k -> new ArrayList<>()); addTo.add(num); if (addTo.size() >= L && addTo.get(0) < smPrime) { smPrime = addTo.get(0); } } else { match(num, regex, dig, howOften - 1, i + 1); } regex.setCharAt(i, asDig); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); N = scanner.nextInt(); K = scanner.nextInt(); L = scanner.nextInt(); int minNum = 1; for (int i = 1; i < N; i++) { minNum *= 10; } int maxNum = minNum * 10 - 1; boolean[] primes = new boolean[maxNum + 1]; Arrays.fill(primes, true); primes[0] = primes[1] = false; for (int i = 2; i * i <= maxNum; i++) { if (primes[i]) { for (int j = 2 * i; j <= maxNum; j += i) { primes[j] = false; } } } for (int i = minNum; i <= maxNum; i++) { if (primes[i]) { String strNum = Integer.toString(i); for (int dig = 0; dig <= 9; dig++) { match(i, new StringBuilder(strNum), dig, K, 0); } if (N == 7) { if (K == 1 && i > 2 * Math.pow(10, 6)) { break; } if (K == 2 && i > 3 * Math.pow(10, 6)) { break; } } } } String mini = ""; for (Map.Entry<String, List<Integer>> entry : M.entrySet()) { List<Integer> values = entry.getValue(); if (values.size() < L) { continue; } if (!values.get(0).equals(smPrime)) { continue; } StringBuilder s = new StringBuilder(); for (int i = 0; i < L; i++) { s.append(values.get(i)).append(" "); } if (mini.compareTo(s.toString()) > 0 || mini.isEmpty()) { mini = s.toString(); } } System.out.println(mini); } }
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #51: Prime digit replacements
You are viewing a single comment's thread. Return to all comments →
JAva code