Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
REエラーで通らなかった
T = int(input())
cnt = 1
def gen_primes(x):
if x < 2: return []
primes = [i for i in range(x)]
primes[1] = 0
for prime in primes:
if prime >= x: break
if prime == 0: continue
for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0
return [prime for prime in primes if prime != 0]
def prime_loop(p, primes):
for i in range(len(primes)):
for j in range(i+1, len(primes)):
if p == primes[i] * primes[j]:
#print("found", primes[i], primes[j])
return primes[i], primes[j]
return 0, 0
for _ in range(T):
N, L = map(int, input().split())
pt = list(map(int, input().split()))
#print(N, L, pt)
primes = gen_primes(N)
primes.sort()
i, j = 0, 0
used_primes = []
for p in pt:
#print(p)
if i == j == 0:
x = prime_loop(p, primes)
i = x[0]
j = x[1]
else:
j = p // i
used_primes.append(i)
i = j
used_primes.append(i)
#print(used_primes)
sorted_used_primes = sorted(set(used_primes))
prime_dict = {}
for i in range(len(sorted_used_primes)):
num = sorted_used_primes[i]
prime_dict[num] = chr(65 + i)
result = ""
for u in used_primes:
result += prime_dict[u]
print("Case #"+str(cnt)+":", result)
cnt += 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.