문제 링크
성능 요약
메모리: 26404 KB, 시간: 192 ms
분류
수학(math), 정수론(number_theory), 소수 판정(primality_test), 에라토스테네스의 체(sieve)
문제 설명
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
문제 풀이 리뷰
- 주어진 조건을 보니 이중 for문으로 돌면 시간 초과가 뜰거같았다
- 그래서 시간복잡도를 최대한 줄이기 위해, 제곱근까지의 범위로 소수를 구했지만 답이 계속 틀렸다 (이유는 모름)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public 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());
for (int i = M; i <= N; i++) {
if(M == 1) continue;
int sqrtI = (int) Math.sqrt(i) + 1;
boolean flag = false;
for (int j = 2; j <= sqrtI; j++) {
if(i%j == 0){
flag = true;
break;
}
}
if(!flag){
System.out.println(i);
}
}
}
}
- 검색을 해보니, 대량의 소수를 판별하는 좋은 알고리즘인
에라토스테네스의 체
가 있었다. (https://www.youtube.com/watch?v=5ypkoEgFdH8)
- 해당 알고리즘을 사용했다
제출 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class main4 {
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());
int[] array = new int[N + 1];
getPrime(array);
StringBuilder sb = new StringBuilder();
for (int i = M; i <= N; i++) {
if(array[i] != 0){
sb.append(i + "\n");
}
}
System.out.println(sb);
}
private static void getPrime(int[] array) {
for (int i = 2; i < array.length; i++) {
array[i] = i;
}
for (int i = 2; i < array.length; i++) {
if(array[i] == 0) continue;
for (int j = i+i; j < array.length; j += i) {
array[j] = 0;
}
}
}
}