[백준] 1929번 : 소수 구하기(에라토스테네스의 체)- 파이썬[Python]

문제

1929번: 소수 구하기

풀이

left,right=map(int,input().split()) list1=[True]*(right+1) if len(list1)>2: list1[0]=False list1[1]=False for i in range(2,right+1): if list1[i]==True: for n in range(2*i,right+1,i): list1[n]=False list2=[i for i in range(left,right+1) if list1[i]==True] for i in list2: print(i)

출처:https://this-programmer.tistory.com/409

에라토스테네스의 체를 이용해서 푸는 문제이다.
에라토스테네스의 체는 기존에 n값이 소수인지 판별할때 2부터 n-1까지 나누어서 판단하는 방식보다 더 효율적인 방식이다. n이 소수인지 판단을 할 때 2의 배수를 전부 지우고 3의 배수를 지우는 식으로 합성수를 모두 지워나간다.
이 과정을 통해 지워지지 않는 수가 소수이다.
이 방법을 통해 시간복잡도를 대폭 줄일 수 있다