pcs88pc0448

投稿した質問数 9

while True:

    num = input("2 이상의 숫자를 입력하세요")

    if not num.isnumeric:

        continue

    num = int(num)

    if num < 2:

        continue

    break

prime_list = [False, False] + [True] * (num - 1)

primes = []

for i in range(2, num + 1):

    if prime_list[i]:

        for j in range(2 * i, num + 1, i):

            # 소수가 아니면 False

            prime_list[j] = False

    

primes = [i for i in range(2, num+1) if prime_list[i] == True]

print(primes)

if num in primes:

    print("소수에요.")

else:

    print("소수가 아닙니다.")

4

사실 이 로직은 소수를 구하는 에라토스테네스의체의 방식을 먼저 이해하고 그걸 어떻게 파이썬으로 로직화 시켰는지에 대한 내용이라 조금 어렵게 느껴지실 수도 있습니다. 아래 위키의 내용을 먼저 살펴보시는것도 이해하시는데 도움이 되실 수도 있을것 같습니다. 

위키피아 에라토스네의 체

위의 위키피아에 있는 이미지가 에라토스네의체가 어떤 식으로 흘러가는지를 아주 간단명료하게 표현하고 있습니다. 일단 어떤식으로 동작하는지를 먼저 이해 했다고 치고 대략적으로 위의 코드에 중요한 부분을 설명하자면....

prime_list = [False, False] + [True] * (num - 1)

최초 prime_list 는 사용자에게 입력된 숫자만큼(num-1) 의 리스트에서 0, 1 은 False 로 설정하고 2부터는 True 로 입력된 숫자만큼 True 설정하게 됩니다. 예를 들어 사용자가 6을 입력했다고 하면..

prime_list = [False, False, True, True, True, True]

이렇게 prime_list 가 초기화 되게 됩니다. 그리고 아래 코드를 보시면 2부터 for 문을 돌면서 수를 체크하게 됩니다.

prime_list = [False, False] + [True] * (num - 1)
primes = []

for i in range(2, num + 1):
    if prime_list[i]:
        for j in range(2 * i, num + 1, i):
            # 소수가 아니면 False
            prime_list[j] = False

최초 if prime_list[i] 는 위에서 True 로 설정되었기 때문에 참이 되고 그 숫자의 배수(2 * i) 를 모두 False 로 설정합니다. 배수는 나눌수 있는 숫자라는 의미기 때문에 소수가 아닙니다. 이 부분이 위의 GIF 이미지에서 최초 빨간색으로 칠해지는 영역이 됩니다. 그렇게 되면 다음 for 문을 돌때 False 로 설정된 배수들은 if 문에 걸리지 않고 그냥 통과하게 됩니다. 이런 알고리즘을 이해하고자 할때는 입력수를 작은수로 입력하고 (예를 들어 5정도..) 그리고 이중 for 문의 i, j 값 그리고 prime_list 의 값을 모두 print 문을사용해서 화면에 출력해보고 직접 눈으로 보면서 이해하는 과정이 도움이 많이 됩니다. 큰 수를 입력하고 확인하려면 너무 복잡해보이기 때문에 작은수 부터 하나씩 입력해보면서 각 변수의 값이 어떻게 변화해 가는지를 직접 확인해보는것이 중요합니다. 

while True:
    num = input("2 이상의 숫자를 입력하세요")
    if not num.isnumeric:
        continue
    num = int(num)
    if num < 2:
        continue
    break

prime_list = [False, False] + [True] * (num - 1)
primes = []

for i in range(2, num + 1):
    if prime_list[i]:
        for j in range(2 * i, num + 1, i):
            # 소수가 아니면 False
            prime_list[j] = False
    print("i={}, j={}, prime_list={}".format(i, j, prime_list))

primes = [i for i in range(2, num+1) if prime_list[i] == True]
print(primes)

if num in primes:
    print("소수에요.")
else:
    print("소수가 아닙니다.")

위의 코드처럼 print 문을 추가해서 현재 내용을 출력해보면서 알고리즘을 이해하는데 도움을 받을 수 있습니다. 위의 코드를 실행해서 입력값으로 5를 입력하고 화면에 출력된 값을 살펴보면...

i=2, j=4, prime_list=[False, False, True, True, False, True] (최초 i 가 2인경우 2의 배수 모두 False)

i=3, j=4, prime_list=[False, False, True, True, False, True] (i 가 3인 경우 리스트에는 5까지만 있으므로 6패스)

i=4, j=4, prime_list=[False, False, True, True, False, True] (위와 같음)

i=5, j=4, prime_list=[False, False, True, True, False, True] (위와 같음)

위와 같은 결과를 얻을 수 있습니다.

결론은 True 의 자릿수를 보면 2, 3, 5 만 남고 입력된 값 5 이하의 소수는 2, 3, 5를 확인할 수 있게 되는 그런 내용입니다. 충분하시지 않으실 수 있겠지만 그래도 도움이 되셨으면 좋겠습니다. 

0

친절하고 정성 가득한 답변 감사합니다. 말씀하신 토대로 천천히 살펴보겠습니다.