백준 1929번 - 소수 구하기(Python)

1929번은 m~n 수 범위 내에서 소수를 찾아 출력하는 프로그램이다. 

 

 

m과 n을 입력하면 사이에 존재하는 소수를 출력해주면 된다. 는 건데 

 

 

참고로(알고있겠지만) 백준 문제 중에 해결에 어려움이 있을 때...  문제 밑에 달린 키워드를 찾아보면 좀 도움이 된다(많이) 

이 문제는 소수를 찾는 방법으로 사용되는 에라토스테네스의 채 방법이 적혀있었고 1을 제외한 2부터 찾아지는 소수로 특정 수를 나누었을 때 나머지가 없다면 약수가 존재한다는 것이기 때문에 합성수를 제외해주면서 소수를 찾아나가는 방식이다. 

그렇다면 이걸 어떻게 구현하느냐?(이게 본론이자 메인임...) 

a, b = map(int, input().split())
        
for i in range(a,b+1):
        
    if i==1:#1은 소수가 아니므로 제외
        continue
            
    for j in range(2,int(i**0.5)+1):
            
        if i%j==0: #약수가 존재(나머지 x) -> 소수가 아님
            break   
                
    else:
        print(i)

먼저 첫 줄에서 m과 n(코드 상에서는 a, b)를 입력받아서 바깥 for 문을 a부터 b까지 수행한다(a~b 사이의 소수를 찾는 거므로) 

1을 제외(소수, 합성수 둘다 아님)하고 해당 범위 내에서 소수를 찾게 되는데, 범위 내의 특정 수 i를 판별하기 위해서는 i를  2부터 제곱근 i(= i^(1/2))까지 나눠보면 알 수 있다 

제곱근의 값이 

1인 경우: 2, 3

2인 경우: 4, 5, 6, 7, 8

3인 경우: 9, 10, 11, 12, 13, 14, 15

4인 경우: 16, 17, 18... 24

5인 경우: 25, 26, 27... 35

으로 나뉘는데

 

예를 들어 15을 코드에 적용한다고 생각해 보면 

안쪽의 for문에서 15을 2로 나눴을 때 나머지가 1이기 때문에 2는 15의 약수가 아니게 되고

for 문의 j 값(나누는 값)이 3으로 증가하게 된다. 

동일한 방식으로 15을 3으로 나누면 나머지가 0이 되어 15을 합성수로 판단되고,

break 문에 걸려 숫자가 출력하지 않게 된다.

15는 약수가 1, 3, 5, 15로 구성되어 있지만 소수는 자기 자신과 1만이 약수로 하는 숫자이므로 1보다는 크고, 자기 자신(예시에서는 15) 사이에 또다른 약수가 발견되면 합성수/발견되지 않으면 소수인 것이다. 이 약수는 대소가 상관없기 때문에 효율적인 코드 구성을 위해서는 가장 작은 값을 적은 시행으로 발견하는 것이 유리하기 때문에 1 초과의 가장 작은 정수 값인 2부터 나누기 연산을 시행하여 소수(합성수) 여부를 판별한다. 

위에 "에라토스테네스의 체"를 설명한 위키 백과의 캡처본에서 맨 마지막 줄을 살펴보면 합성수들은 모두 자신의 제곱근의 수보다 작은 수를 약수로 가지기 때문에 제곱근(루트) 값을 이용하여 약수 찾기를 수행하면 더 빠르게 합성수 여부를 판단할 수 있다.