[215] D - Coprime 2

https://atcoder.jp/contests/abc215/tasks/abc215_d

D - Coprime 2

주어진 범위 내에서, 주어진 수들과 모두 서로소(최대공약수가 1)가 되는 값를 찾는 문제이다.

Solution

N,M = map(int,input().split())
A = list(map(int,input().split()))
maxA = max(max(A),M)
 
k = [True] * (maxA+1)
isprime = [True] * (maxA+1)
prime = []

for a in A: 
    k[a] = False

for i in range(2,maxA+1):
    if not isprime[i]:
        continue
    for j in range(i*2,maxA+1,i):
        isprime[j] = False
        k[i] = k[i] and k[j]
    if not k[i]:
        prime.append(i)

for p in prime:
    for j in range(p*2,M+1,p):
        k[j] = k[j] and k[p]

ans = [1]
for i in range(2,M+1):
    if k[i]:
        ans.append(i)

print(len(ans))
for i in ans:
    print(i)

• 가장 큰 값의 크기를 길이로 가지는 리스트 k를 True로 다 채운다.
• 받은 숫자들은 제외해야 하기 때문에 False를 넣는다.
• 2부터 숫자를 끝까지 살피도록 for문을 돌린다.
  • 해당 수의 배수에 isprime = False로 할당하여, 소수를 고른다.
  • k에는 받은 수들의 배수나 약수가 들어가면 안되므로, and를 사용해서 걸러준다. k[i]가 받은 수라면 배수를 거르는 것이고, k[j]가 받은 수라면 약수를 거르는 것이다.
  • 만약 k[i]=False라면, prime에 저장해둔다.
• 저장한 prime들의 배수를 and로 한번 더 걸러준다.
• k에 True로 남는 것들을 ans에 넣어주고, 출력한다.

 

배수와 약수를 and로 거르는 방법이 독특하다. 기억해서 나중에 사용할 만하다.