1929번 소수 구하기
문제
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력
한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.
예제 입력 1
3 16
예제 출력 1
3
5
7
11
13
나의 풀이
// 반복문은 시간초과
int a = 0; // 나눠지는 수
for(int i=0; i<=N-M; i++) {
a = M+i;
int cnt = 0;
for(int j=2; j<=a; j++) {
if(a%j == 0) {
cnt++;
}
}
if(cnt == 1) {
System.out.println(a);
}
}전에 풀었던 문제처럼
반복문을 통해 1부터 해당 숫자까지 나눠보고
cnt를 통해 나눠진 횟수를 +시켜줬다
그리고 cnt가 1인 것만 출력하는 코드를 작성했다
결과는
시간초과...
아마도 숫자 하나가 소수인지 구하는 데 2~i 연산을
총 N-M번은 해야 한다 숫자의 크기는 1,000,000...
시간초과에 대한 질문 게시판을 검색하던 도중 에라토스테네스의 체를 알게 되었다
에라토스테네스의 체
위키백과
기본 개념은 다음과 같다
2부터 원하는 구간까지의 배열을 생성하고
반복을 통해 2를 선택한 뒤 2의 배수를 모두 제거한다
이후로 모든 숫자를 이렇게 반복하면
소수만 남게 된다
JAVA구현은 다음과 같다
1. 0~N까지의 boolean형 배열 생성
boolean형 배열을 N번까지 생성한다
배열은 0부터 시작하므로 arr[N+1]로 작성
0은 입력 범위가 아니고, 1은 소수가 아니므로 항상 true값을 반환하도록 한다
boolean arr[] = new boolean[N+1]
arr[1] = true;2. 반복문을 통해 소수가 아닌 값을 처리
2부터 시작하여 N까지 배수들을 지워나가는 과정을 반복문 처리한다
2부터 N까지 진행하면서,
i가 2면 자신을 제외하고, 2*2, 2*3 ... 모두 true값으로 변경한다
i는 굳이 i<=N이 아닌, i<N 도 성공으로 뜬다
아마 i*j<N이기 때문이 아닐까
for(int i=2; i<=N; i++) {
for(int j=2; i*j<=N; j++) {
arr[i*j] = true;
}
}
위의 코드를 실행해 보면 이렇게 뜬다
2는 false, 3도 false 17까지 false다
각 수의 배수들은 true 처리된다
3. 반복문을 통해 M~N까지 출력
for(int i=M; i<=N; i++) { // M부터 N까지
if(!arr[i]) { // arr[i]가 false일 때 true로
System.out.println(i);
}
}arr[i]가 false일 경우에 true값으로 바꿔주며 출력한다
반복문보다 훨씬 빠르다
에라토스테네스의 체는 O의 시간복잡도를 가진다고 한다
다음은 나의 코드
실패
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class _1929_소수구하기 {
public static void main(String[] args) throws IOException {
// M이상 N이하의 소수를 모두 출력하는 프로그램 작성
// BufferedReader 사용
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
// 반복문은 시간초과
int a = 0; // 나눠지는 수
for(int i=0; i<=N-M; i++) {
a = M+i;
int cnt = 0;
for(int j=2; j<=a; j++) {
if(a%j == 0) {
cnt++;
}
}
if(cnt == 1) {
System.out.println(a);
}
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class _1929_소수구하기 {
public static void main(String[] args) throws IOException {
// M이상 N이하의 소수를 모두 출력하는 프로그램 작성
// BufferedReader 사용
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
// 에라토스테네스의 체 공부
// 1. 배열 생성 및 초기화
boolean arr[] = new boolean[N+1]; // 허용 범위 만큼의 배열 생성 = boolean형
arr[1] = true; //1은 소수가 아니므로 패스
// 2. 구하고자 하는 숫자의 범위? M ~ N
// 3. 반복문을 돌며 i=2부터 시작, 배수들을 모두 true값으로 변경
for(int i=2; i<=N; i++) {
for(int j=2; i*j<=N; j++) {
arr[i*j] = true;
}
}
// System.out.println(Arrays.toString(arr));
for(int i=M; i<=N; i++) { // M부터 N까지
if(!arr[i]) { // arr[i]가 false일 때 true로
System.out.println(i);
}
}
}
}
