카테고리
세부 분야
프로그래밍 언어
해결 여부
해결됨
19.10.17 11:36 작성 조회수 72
1
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):
prime_list[j] = False
primes = [i for i in range(2, num+1) if prime_list[i] == True]
print(primes)
if prime_list[i]:
for j in range(2 * i, num + 1, i):
여기서 prime_list에 i를 넣어주는거부터 이해가 안가요
답변 안올라와서 다시 올립니다.
답변을 작성해보세요.
1
남박사
지식공유자2019.10.17
prime_list 에 i 를 넣어주는건 prime_list 가 리스트 형태의 자료구조이고 이 리스트 형태의 prime_list 의 몇번째 값을 얻기 위해서 [i] 이렇게 넣어주는 것 입니다.
만약 num 이 5 라고 가정해보고 얘기를 해보겠습니다.
prime_list 는 최초 [False, False, True, True, True, True] 으로 초기화가 됩니다.
prime_list는 6개의 값을 가진 리스트 형태이고 여기서 내가 2번째 값을 확인하기 위해선 prime_list[2] 이런식으로 접근해야 합니다.
어쨌든 위의 prime_list 값은 앞에서부터 0, 1, 2, 3, 4, 5 의 숫자의 순서대로라고 보시면 되고 여기서 False 는 소수가 아님을 의미하고 True 는 소수임을 의미하는건데 소수를 구하는 방식중 한가지인 에라토스테네스의체의 방식을 사용했기 때문에 이런식으로 작성된 것입니다. 우리는 사용자가 입력한 숫자가 아직 소수인지 아닌지 알 수 없기 때문에 최초에 모든 값을 확인해야하기 때문에 0과 1을 제외하고 모든 자리의 수를 True 로 초기화 해놓은 것입니다.
if prime_list[i] 는 prime_list 리스트에서 i 번째의 값을 의미하는건데 최초 [False, False, True, True, True, True] 인 상황에서 if prime_list[2] 의 값은 True 입니다.
그래서 if prime_list[i] 는 True 로서 참이 되게되고 그 다음의 로직을 살펴보자면
for j in range(2 * i, num + 1, i):
prime_list[j] = False 이 부분에 의해 해당 숫자의 배수값을 for문으로 반복하며 모두 False로 설정하게 됩니다. 배수는 다른말로 나눌 수 있는 의미가 되기 때문에 소수가 아닌게 되는거죠. 그렇게 prime_list 의 값이 False 로 설정되면 이미 이 자리에 해당하는 숫자는 소수가 아님이 판명 난 상황이기 때문에 질문하신 if prime_list[i] 의 조건에 걸리지 않고 그냥 통과하게 되는 의미 입니다.
그렇게 반복을 하다보면 이 for문을 반복한 값만 출력해보면
[False, False, True, True, True, True] = 최초 i 가 2 인경우
[False, False, True, True, False, True] = i 가 3인 경우 (3의 배수면 6인데 입력된 값이 5기때문에 대상이 없음)
[False, False, True, True, False, True] = i 가 4인 경우 (위와 같음)
[False, False, True, True, False, True] = i 가 5인 경우 (위와 같음)
결론은 True 의 자릿수를 보면 2, 3, 5 만 남고 입력된 값 5 이하의 소수는 2, 3, 5를 확인할 수 있게 되는 그런 내용입니다.
사실 이 로직은 소수를 구하는 에라토스테네스의체의 방식을 먼저 이해하고 그걸 어떻게 파이썬으로 로직화 시켰는지에 대한 내용이라 조금 어렵게 느껴지실 수도 있습니다. 아래 위키의 내용을 먼저 살펴보시는것도 이해하시는데 도움이 되실 수도 있을것 같습니다. 궁금하신점 있으시면 또 질문주세요.
답변 1