[파이썬] n 이하의 소수 찾기

소수판별 문제를 풀다가 문득 소수를 찾는 코드를 짜보고 싶어졌다.

 

코드 공개

n = int(input("자연수를 입력하시오: "))
breaktime = 0
if n == 1:
    print("%d이하의 소수는 없습니다."%(n))
else:
    PrimeList = [2]
    while PrimeList[-1] < n:
        for i in range(1,n+1):
            for j in PrimeList:
                if (PrimeList[-1]+i) % j == 0:
                    breaktime += 1
                    break
            if breaktime == 0:
                PrimeList.append(PrimeList[-1]+i)
                break
            else:
                breaktime -= 1
    while PrimeList[-1] > n:
        PrimeList.pop()
    print(PrimeList)

문제점

 잘 동작하긴 하지만 큰수를 넣으면 n보다 큰 소수들이 출력되는 문제가 있어 18, 19 줄을 추가하여 강제로 빼버려야 했다. 아래 코드는 내 코드를 보시고 교수님께서 그러한 문제점을 보완하신 코드이다.

교수님 코드

n = int(input("자연수를 입력하시오: "))
breaktime = False
if n == 1:
    print("%d이하의 소수는 없습니다."%(n))
else:
    PrimeList = [2]
    while PrimeList[-1] < n:
        if breaktime==True:
            break
        for i in range(1,n+1):
            if (PrimeList[-1]+i) > n:
                breaktime=True
                break
            for j in PrimeList:
                if (PrimeList[-1]+i) % j == 0:
                    break
            else:
                PrimeList.append(PrimeList[-1]+i)
                break
    print(PrimeList)

해당 문제점도 사라졌고 전보다 3자가 보았을때 해석하기도 훨씬 쉬워졌다. 벽을 느꼈다.

해석

n = int(input("자연수를 입력하시오: "))
breaktime = 0
if n == 1:
    print("%d이하의 소수는 없습니다."%(n))

입력받은 자연수가 1일때는 예외사항으로 미리 정해둔 결과를 출력하도록 한다.

breaktime 이란 변수는 그외의 자연수가 입력되었을때 계산중에 사용된다. 밑에서 확인.

else:
    PrimeList = [2]
    while PrimeList[-1] < n:
        for i in range(1,n+1):
            for j in PrimeList:
                if (PrimeList[-1]+i) % j == 0:
                    breaktime += 1
                    break
            if breaktime == 0:
                PrimeList.append(PrimeList[-1]+i)
                break
            else:
                breaktime -= 1

입력받은 자연수가 1이 아니라면 다음의 논리에 따라 소수 리스트를 만들어 나간다.

else가 실행된다면 입력받은 자연수는 2이상이므로 2가 들어가있게끔 기본 소수리스트를 만들어준다.

1. i 가 1부터 n까지의 자연수이고 j가 리스트의 요소들일때, 소수리스트의 마지막 수에 i를 더해서 소수리스트의 모든 요소들로 한번씩 나누어본다.

2. 만약 리스트마지막수 + i 가 j로 나누어 떨어진다면 j라는 인수를 가지므로 소수가 아니다. 그러므로 소수가 아님을 표시하는 작업으로 미리지정해둔 breaktime변수에 1을 더하고 반복문을 깬다.

3. breaktime 변수의 값을 확인하여 0이라면 j로 나누어떨어진적이 없다는 의미 즉 소수이므로 리스트에 추가하고 바깥 for문을 깬다. while조건에 따라 i를 1부터 다시 하여 소수를 찾거나 소수찾기를 멈춘다. 

4. breatime이 1이라면 소수가 아니므로 breaktime을 0으로 되돌리고 다음 i에 대해 1~4번 작업을 다시한다.

    while PrimeList[-1] > n:
        PrimeList.pop()
    print(PrimeList)

소수리스트의 마지막 요소가 n보다 크면 계속해서 빼준다.

그리고 리스트를 출력한다.

주의할점은 이 코드도 else에 포함되기 때문에 들여쓰기를 지켜주어야 한다.