HMMT 十一月 2018 · 冲刺赛 · 第 34 题
HMMT November 2018 — Guts Round — Problem 34
题目详情
英文原题
- [ 20 ] A positive integer is called primer if it has a prime number of distinct prime factors. A positiveinteger is called primest if it has a primer number of distinct primer factors. A positive integer iscalled prime-minister if it has a primest number of distinct primest factors. Let N be the smallestprime-minister number. Estimate N .
( )
N E
An estimate of E > 0 earns b 20 min , c points.
E N
解析
英文解析
- [ 20 ] A positive integer is called primer if it has a prime number of distinct prime factors. A positiveinteger is called primest if it has a primer number of distinct primer factors. A positive integer iscalled prime-minister if it has a primest number of distinct primest factors. Let N be the smallestprime-minister number. Estimate N .
N E
An estimate of E > 0 earns b 20 min , c points.
E N
Proposed by: Yuan Yao
4 3 3
Answer: 2 · 3 · 5 · 7 = 378000
q s
One heuristic for estimating the answer is that numbers of the form p r for primes p, q, r, s withp 6 = r, q 6 = s are primest. Thus, primest numbers are not very rare, so we can expect the answer to berelatively small with only a few distinct prime factors.
from operator import *
primes = []
primers = []
primests = []
for i in range(2,3000):
prime_factors = 0
primer_factors = 0
temp = ifor x in primes:
if x > temp:
breakif temp % x == 0:
prime_factors += 1
while temp % x == 0:
temp = temp // xif (prime_factors == 0):
primes.append(i)
continueelif (prime_factors in primes):
primers.append(i)
for x in primers:
if i % x == 0:
primer_factors += 1
if (primer_factors in primers):
primests.append(i)
def product(L):
ans = 1
for i in L:
ans*= ireturn ansdef sum_prime_product(L, curr = ()):
if (L == ()):
#print(curr)
if len(curr) in primes:
return product(curr)
return 0
return sum_prime_product(L[1:], curr + (L[0],)) + sum_prime_product(L[1:], curr)
def count_primests(L, curr = ()):
if (L == ()):
if (sum_prime_product(curr) in primers):
return 1
return 0
ans = 0
for i in range(0,L[0]+1):
ans += count_primests(L[1:], curr+(i,))
return ansdef compute(L):
ans = 1
for i in range(len(L)):
ans *= (primes[i]L[i])
return ansdef find_best(M, best = 220 * 3**5, curr = ()):
num = compute(curr)
if (num > best):
return Falseif (count_primests(curr) in primests):
print(num, curr)
return numfor i in range(1,M):
result = find_best(M, best, curr + (i,))
if (result == False):
breakelif (result < best):
best = resultreturn bestprint("Answer:", find_best(30))