에라토스테네스의 체 c++ (1) 썸네일형 리스트형 [C / C++] 백준 1929번 - 소수 구하기 / 에라토스테네스의 체 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net ✅ 문제 설명 정수 M과 N을 입력하면, M ~ N 사이의 소수를 출력하는 문제이다. ✅ 알고리즘 설명 처음에는 단순하게 생각하여, M ~ N을 차례로 하나씩 나눠지는 수가 있는지 검사하여 출력하는 방식을 사용했다. 그러나 이 방법을 사용하면 시간복잡도가 O(N^2)으로 시간초과가 나게 된다. 따라서 이 문제에서는 '에라토스테네스의 체' 방식을 사용했다. 💡 에라토스테네스의 체 (Sieve of Eratosthenes) 💡 소수.. 이전 1 다음
