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.
Project Euler #49: Prime permutations
Project Euler #49: Prime permutations
Sort by
recency
|
24 Discussions
|
Please Login in order to post a comment
from collections import OrderedDict, defaultdict from math import sqrt
code_p = {0: 2, 1: 3, 2: 5, 3: 7, 4: 11, 5: 13, 6: 17, 7: 19, 8: 23, 9: 29}
N_input, K = map(int, input().split())
n = N_input N = N_input - 1 if N_input in [10**_ for _ in range(3, 7)] else N_input
SIEVE_LIMIT = 10**(len(str(N)))-1 primes_sieve_array = [0] * (SIEVE_LIMIT + 1) # 0 for prime, 1 for composite
for i in range(2, len(primes_sieve_array)):
def rootval(num_val): s = 1 temp_num = num_val if temp_num == 0: s *= code_p[0] else: while temp_num > 0: s *= code_p[temp_num % 10] temp_num //= 10 return s
primes_d = OrderedDict() k_vals = OrderedDict()
for j in (i_prime_candidate for i_prime_candidate in range(2, len(primes_sieve_array)) if primes_sieve_array[i_prime_candidate] == 0 and i_prime_candidate >= 1487):
for i_start_prime in k_vals: if len(k_vals[i_start_prime]) < K - 1: continue
100% python
itertools permutations, and groupby are very helpful things to learn for this one!
Solution for n=1000000, k=3
If you are having timout issues, I recommend implementing sieve to get the relevant prime numbers, and using itertools permutations. The key is not to run itertools on every prime. As you go along, apply the same permutation list to all the primes in the list to optimize speed. I recommend splicing only the larger primes. Good luck!