[BOJ/백준] 1837 - 암호제작 (Python)

문제

문제링크

두 소수 p와 q의 곱을 비밀키로 둔다. 두 소수가 각각 K보다 작으면 좋지 않은 암호이다.

좋은 암호이면 첫째 줄에 GOOD을 출력하고 좋지 않은 암호이면 BAD와 둘 중 작은 소수을 공백으로 구분해 출력한다.

 

풀이

에라토스테네스의 체를 사용한다.

1부터 K-1까지 중에서 소수만 True로 남기는 리스트 is_prime을 생성한다. 이때 0과 1은 소수가 아니므로 False로 둔다.

어떤수가 합성수면 반드시 √K 이하의 약수를 가지므로 range(2, int(K**0.5)+1)로 둔다.

i*k (k<i)일 떄는 이미 더 작은 소수들의 배수로 지워졌기 때문에 내부 for문의 범위는 range(i*i, K, i)이다.

이제 i의 배수는 False로 바꾼다.

is_prime 리스트에서 index와 value를 꺼내 True일 경우만 인덱스를 primes에 넣는다.

이제 primes에는 K 이하의 소수만 들어있다.

P는 무조건 소수의 곱이므로 primes 안의 요소 중 하나라도 P의 약수면 나쁜 암호이다.

 

코드

P, K=map(int, input().split())

is_prime=[1]*K
is_prime[0]=is_prime[1]=0
for i in range(2, int(K**0.5)+1):
    if is_prime[i]:
        for j in range(i*i, K, i): is_prime[j]=False
    
primes=[i for i, val in enumerate(is_prime) if val]
for prime in primes:
    if P%prime==0: print('BAD', prime); break
else: print('GOOD')