[Python] 1에서 100까지 숫자들 중 소수 (Prime Number)만 찾아서 출력하기 파이썬 프로그램 예제

 

무한히 많은 숫자들 중 가장 신비로운 수 중의 하나가 바로 소수입니다. 영어로 Prime Number라고 하고, 1과 자기 자신을 제외한 어떤 수로도 나눠지지 않는 수를 말합니다. 심지어 세상 모든 수는 소수이거나 소수와 소수의 곱으로만 이루어져 있다고 표현하기도 합니다.

 

소수는 어차피 자기 자신을 제외하면 약수가 없으니 그렇다 치지만, 예를 들어 8이면 2 X 2 X 2로 표현할 수 있으니 소수와 소수의 곱으로 표현됩니다. 따라서 세상의 모든 수는 소수이거나 소수의 곱으로만 이루어졌다는 표현은 정확합니다.

 

일하다가 갑자기 떠올랐습니다. “주어진 범위 안에 있는 소수를 모두 찾아내는 프로그램을 만들면 재미있겠다.” 그래서 만들어봤습니다. 코딩의 내용은 다음과 같습니다.

 

prime_numbers = []
other_numbers = []

for x in range(2, 101):
    if x == 2 or x == 3:
        prime_numbers.append(x)
    else:
        if x % 2 == 0:
            other_numbers.append(x)
        else:
            for i in range(3, x-1):
                if x % i == 0:
                    other_numbers.append(x)
                    break
                else:
                    continue
            if x not in other_numbers:
                prime_numbers.append(x)

print(prime_numbers)
print(len(prime_numbers))

 

아시다시피 알고리즘은 누가 어떤 의도로 만드느냐에 따라 달라집니다. 저는 좀 단순하고 무식한 방법으로 이해하기 편하게 코딩하는 편이라 실력이 뛰어나신 분들은 더 심플하고 간결하게 만들 수도 있을 것입니다.취미로 공부하고 있는 저는 이 정도만 해도 충분합니다.

 

반응형

 

코딩 내용을 짧게 주석을 달아 설명 드리겠습니다.

#비어있는 리스트를 만듭니다.
prime_numbers = [] #소수 리스트
other_numbers = [] #소수가 아닌 숫자 리스트

#2부터 100까지 숫자들을 하나씩 검사
for x in range(2, 101):
    #2와 3은 무조건 소수로 직행
    if x == 2 or x == 3:
        prime_numbers.append(x)
    else:
        #짝수는 무조건 소수가 아닌 숫자 리스트로 직행
        if x % 2 == 0:
            other_numbers.append(x)
        else:
            #3부터 자기 자신 직전까지 숫자들로 나눔
            for i in range(3, x):
                #어느 하나라도 나눠지면 소수가 아닌 숫자리스트로 직행
                if x % i == 0:
                    other_numbers.append(x)
                    break
                else:
                    #나눠지지 않으면 자기 자신 직전까지 계속
                    continue
            #for문을 빠져나온 숫자가 소수가 아닌 숫자리스트로 직행했는지 여부 판단
            if x not in other_numbers:
                #어느 것에도 나눠지지 않고 소수가 아닌리스트에도 없다면 소수로 판단
                prime_numbers.append(x)

print(prime_numbers) #소수 리스트 출력
print(len(prime_numbers)) #소수 개수 출력

제가 고안한 알고리즘은 다음과 같습니다.

1) 소수 리스트와 소수가 아닌 숫자 리스트를 만든다.

2) 반복문으로 범위를 지정하여 하나씩 input 받는다.

3) 입력된 숫자가 2나 3이면 소수가 아닌 숫자 리스트로 보낸다.

4) 입력된 숫자가 짝수면 소수가 아닌 숫자 리스트로 보낸다.

5) (3)과 (4)를 통과했다면 다시 반복문으로 입력된 숫자가 자기 자신 직전까지 숫자들로 하나씩 나눠본다.

6) (5)에서 어느 하나라도 나눠지면 소수가 아닌 숫자 리스트로 보낸다.

7) 반복문을 빠져나왔다면 나눠져서 빠져나온 것인지,나눠지지 않아서 빠져나온 것인지를 판단한다.

8) 최종적으로 자기 자신을 제외한 어떤 숫자로도 나눠지지 않았다면 소수 리스트로 보낸다.

9) 소수 리스트와 개수를 출력한다.

 

결과는 이렇게 출력됩니다. 결과 출력에 1초도 안 걸리는 것 같습니다. 1부터 100까지 숫자들 중 소수는 25개가 있네요.

 

PS C:\Python_practice> & "C:/Program Files/Python310/python.exe" c:/Python_practice/test3.py

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

25

PS C:\Python_practice>

 

그럼 범위를 늘려서 1부터 1,000까지 숫자들 중 소수를 찾아볼까요? 101을 1001로만 바꾸면 됩니다. 결과는 다음과 같고 역시 1초도 안 걸리는 것 같습니다. 1부터 1000까지 숫자들 중 소수는 총 168개가 있네요.

 

PS C:\Python_practice> & "C:/Program Files/Python310/python.exe" c:/Python_practice/test3.py

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,

151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

168

PS C:\Python_practice>

 

---

 

끝으로…

 

프로그램 언어 공부는 이렇게 갑자기 만들고 싶은 것이 있어야 실력이 향상됩니다. 함수를 잔뜩 외우거나 한다고 늘지 않습니다. 직접 프로그램을 만들어 보고, 책이나 인터넷에서 남이 만든 코딩을 영어 해석하듯이 해석해보고, 때론 응용도 하면서 씹고, 뜯고, 맛보고, 즐기고 해야 합니다. 저도 그랬습니다. 20여년 전 처음 프로그램 언어 공부할 때 함수 설명만 잔뜩 있는 책을 한 권 보고 나서 가장 먼저 든 생각은 “그래서 뭐 어쩌라고. 이제 뭘 해야 되지?” 였습니다.

 

저는 정답이라고 글을 쓰거나 자랑하려고 올리는 것이 아닙니다. 저는 부족한 것 투성이임을 누구보다 잘 알고 있습니다. 그래서 공부를 놓지 못하고 계속하는 것입니다. 반복해서 말씀 드리지만, 저도 처음 공부 시작할 때 누군가에게 도움을 받았으니, 저도 누군가에게 도움을 드리고자 할 뿐입니다. 시작할 때의 그 막막함과 답답함을 저는 너무 잘 알고 있으니까요.