Python 응용문제 - 소수 판별 및 응용 프로그램

소수는 약수가 1과 자기 자신밖에 없는 수를 말한다.

파이썬 반복문을 활용해 입력받은 수가 소수인지 판별하는 프로그램과 몇 가지 응용 프로그램을 작성해보자.

 

사실 어떤 수가 소수인지 아닌지 판별하는 방법은 단순하다. 2부터 자기자신까지 전부 나눠보면 된다.

반복문으로 구현하면 간단하다.

 

n = int(input("숫자 입력>> "))

i = 2

while n % i != 0:
    i += 1

if i == n:
	print("소수입니다.")
else:
	print("소수가 아닙니다.")

 

while문은 n이 i로 나누어 떨어지지 않는 동안 i를 1씩 더하는 동작을 반복한다.

 

i는 계속 1씩 증가하다보면 언젠가는 n과 같아지게 되고, n은 반드시 자기 자신과는 나누어 떨어지므로,

while문은 아무리 많이 돌아도 i가 n이 되는 순간 반복을 멈춘다.

 

만일 i가 n이 되기 전에 n이 나누어 떨어져서 while문의 반복이 멈춘다면,

n은 1과 자기 자신 이외에 나누어 떨어지는 수가 있다는 의미이고,

그것은 곧 n이 소수가 아님을 의미한다.

 

따라서 while문의 반복이 멈춘 후 i의 값을 검사하면 n이 소수인지 아닌지 판별할 수 있다.

i가 n과 같으면 자기 자신 외에 나누어 떨어지는 수가 없다는 의미이므로 소수가 맞고,

i가 n과 다르면 (아마 n보다 작을 것이다) 중간에 나누어 떨어졌다는 의미이므로 소수가 아니다.

 

사실 while의 조건식에서, i를 √n 까지만 증가시켜서 나누어 떨어지는지 확인하면 된다.

4 * 8이나 8 * 4이나 똑같기 때문이다.

 

다만, 본문에서는 "그냥 2부터 자기보다 작은 수들로 싹 나눠보면 되는거 아냐?" 라는 생각을 코드로 구현하는 것에 초점을 맞추기 위해 조건식을 n까지로 설정해 놓았다.

 

 

이제 소수를 구하는 몇 가지 응용 프로그램을 작성해보자. 간단한 응용이다.

 

먼저, 숫자 n을 입력받아 총 n개의 소수를 2부터 순서대로 출력하는 프로그램이다.

찾아낸 소수의 개수를 세어야 하므로 counter 변수가 필요할 듯 하다.

n = int(input("출력할 소수의 개수 입력>> "))

count = 0
tmp = 2

while count < n:
    
    i = 2
    while tmp % i != 0:
   	    i += 1
    if tmp == i:
        count += 1
        print(tmp, end=' ')
    
    tmp += 1

tmp를 2부터 1씩 증가시키면서 소수인지 판별한다.

소수가 맞다면 값을 출력하고 count 변수를 1 증가시킨다.

while문을 돌다가 count가 n(입력한 값. 개수)과 같아지면 반복을 종료한다.

 

결과는 다음과 같다.

출력할 소수의 개수 입력>>  4
>> 2 3 5 7

 

 

이번엔 n을 입력받고 n보다 작은 모든 소수를 출력해보자.

비슷하지만 구현 방법이 다르다. 이러한 응용에 익숙해져야 한다.

n = int(input("값 입력>> "))

tmp = 2

while tmp < n:
    
    i = 2
    while tmp % i != 0:
   	    i += 1
    if tmp == i:
        print(tmp, end=' ')
    
    tmp += 1

 

결과는 다음과 같다.

값 입력 >> 30
>> 2 3 5 7 11 13 17 19 23 29

 

 

여담으로, 소수를 판별하는 알고리즘은 수행 속도가 느린 편이며, 빠르게 판별하는 방법도 없다고 알려져 있다.

때문에 소인수분해와 같이 소수를, 혹은 나누기 연산을 활용하는 방식은 보안 분야에서 많이 쓰인다.

암호화된 키나 데이터를 알아내는데 오래 걸리기 때문이다.