코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
for (int i = N; i <= M; i++) {
int temp = 0;
// 목표 수(N)을 1부터 N까지 모두 나눠보고
for (int j = 1; j <= i; j++) {
if ((i % j) == 0) {
temp++;
}
}
// 딱 떨어지는 횟수가 2 이하인 수만 출력
if (temp < 3) {
System.out.println(i);
}
}
}
}
Java
복사
처음에 완전탐색으로 풀었는데 시간초과가 났다.
1 ≤ M ≤ N ≤ 1,000,000 로 2초 제한이었다.
for문을 2번 돌렸는데, 1에서 i까지 모든 수를 나눠보는 방식을 채택한게 문제였다. 최악은 1,000,000^2번 연산이라..
에라토스테네스의 체
이 방식이 유명한 소수 판별 알고리즘이라고 한다.
어떤 수의 소수 여부를 확인할 때는, 특정 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다. 수가 수를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N제곱근 이하이기 때문이다.
에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.
1.
배열을 생성하여 초기화한다.
2.
2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
3.
2부터 시작하여 남아있는 수를 모두 출력한다.
다시 풀었는데 처음에 M이랑 N도 반대로 넣었었다.. 시력 이슈..
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
boolean[] isPrime = new boolean[N + 1];
// 초기화 - 0, 1은 소수 X. 지우기
isPrime[0] = true;
isPrime[1] = true;
// i의 배수를 모두 판별함
for (int i = 2; i * i <= N; i++) {
// 아직 안지워진 수에 대해
if (!isPrime[i]) {
// i의 배수라면 모두 지우기
for (int j = i * i; j <= N; j += i) {
isPrime[j] = true;
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = M; i <= N; i++) {
if (!isPrime[i]) {
sb.append(i).append("\n");
}
}
System.out.println(sb);
}
}
Java
복사