에라토스테네스의 체1 [Kotlin] BOJ 1929. 소수 구하기 (ft. 에라토스테네스의 체) 출처https://www.acmicpc.net/problem/1929 문제M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 풀이1. 소수란?1과 자기 자신만을 약수로 가지는 수ex) 2, 3, 13.... 2. 소수를 구하는 방법?a. 각 수마다 for문으로 소수인지 아닌지 구하는 방법 -> 하나하나 구해야 하므로 시간복잡도가 높다! O(N) b. 에라토스테네스의 체 -> 제곱근까지만 순회하므로 시간복잡도가 낮다! O(NlogN) 2부터 소수를 구하고자 하는 구간의 모든 .. 2024. 7. 3. 이전 1 다음
