해당 문제는 1929번의 소수 구하기 문제와 유사하므로 풀이 과정은 생략하겠다. [python] 백준 1929번 소수 구하기 문제 요약 및 풀이 M이상 N이하의 소수를 모두 출력 이 문제 같은 경우 1부터 ~ 1,000,000까지 소수인지 아닌지 일일이 검사한다면 시간 초과가 걸리게 될 것이다. 그렇기에 에라토스테네스의 체라 begin-dev-awos.tistory.com 코드!!👌👌 n = 123456*2 # 0, 1 = False, 소수는 2부터 시작이므로 True 로 설정 a = [False, False] + [True] * (n - 1) primes = [] for i in range(2, n + 1): if a[i]: primes.append(i) for j in range(2 * i, n + ..

문제 요약 및 풀이 M이상 N이하의 소수를 모두 출력 이 문제 같은 경우 1부터 ~ 1,000,000까지 소수인지 아닌지 일일이 검사한다면 시간 초과가 걸리게 될 것이다. 그렇기에 에라토스테네스의 체라는 알고리즘을 쓸 예정이다. 밑의 gif 파일을 보자. 이 gif 파일을 보면 2부터 120사이의 소수를 구하는데 2의 배수, 3의 배수... N의 배수를 검사하는 것을 볼 수 있다. 해당 배수들을 제거하게 되면 소수를 찾을 수 있다. '에라토스테네스의 체'의 시간복잡도는 O(Nlog(logN))이다. 일단 M과 N의 제한은 (1 ≤ M ≤ N ≤ 1,000,000) 이기 때문에 1부터 1,000,000까지의 소수를 미리 구해놓고 M과 N사이의 소수를 반환시켜줄 것이다. N의 배수를 제거해야 되기 때문에 b..