오늘의 키워드
•
소수 판별
•
에라토스테네스의 체
문제 파악 및 풀이
에라토스테네스의 체(Eratosthenes' sieve)
: 에라토스테네스의 체는 범위 내에서 소수를 빠르고 효율적으로 찾는 알고리즘
1.
찾고자 하는 범위만큼의 숫자 리스트 생성
2.
2부터 자기 자신을 제외한 2의 배수를 삭제
3.
다음 숫자(3)로 이동하여 반복한다.
4.
남는 숫자들을 모두 소수로 판단한다.
시간 복잡도는 로 효율적이다.
import java.util.Scanner;
class Main {
public static boolean[] isCheck;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
isCheck = new boolean[n + 1];
for (int i = 2; i <= Math.sqrt(n); i++) {
if (isCheck[i]) continue;
for (int j = i * i; j <= n; j += i) {
isCheck[j] = true;
}
}
for (int i = m; i <= n; i++) {
if (1 < i && !isCheck[i]) System.out.println(i);
}
}
}
Java
복사
오늘의 회고
어려웠던 점
1.
처음에는 단순 반복문을 사용했지만, 시간 초과가 발생하여 효율성의 중요성을 다시 한 번 깨달았다.
개선점
1.
시간 복잡도를 미리 고려해보는 습관을 기를 필요가 있다.