백준 #1929 java 2023.01.25

소수 구하기 문제!

소수찾기, 소수, 소수구하기까지... 소수 박사가 된 느낌이다.

 

package boj_basic.step8;

import java.util.Scanner;

public class Q1929 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int M = sc.nextInt();
		int N = sc.nextInt();
		
		int[] arr = new int[N+1];		
		int num = 0;
		for(num = M; num<=N; num++) {
			if(num ==1)
				arr[num]=1;
			for(int i = 2; i<num; i++) {
				if(num%i==0)
					arr[num]=1;
			}
		}
		
		for(int i = M; i<=N; i++) {
			if(arr[i]==0) {
				System.out.println(i);
			}
		}

	}

}

처음 작성했던 코드. 이클립스로 돌렸을 때 답도 잘 나왔다. 정답률이 26%인거에 비해 쉬워서 뭐지...? 했는데 역시나 시간초과가 떴다. 정답률이 낮은 이유가 있었군..ㅎ

 

찾아보니까 "에라토스테네스의 체"라고 소수를 빨리 구할 수 있는 방법이 있다고 한다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 

대충 요런 알고리즘..^^

자세한 내용은 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

package boj_basic.step8;

import java.util.Scanner;

public class Q1929_1 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int M = sc.nextInt();
		int N = sc.nextInt();
		
		int[] arr = new int[N+1];		
		int num = 0;
		
		arr[1]=1; //1은 소수 아님. 미리 배열에 1로 저장
		
		for(num = 2; num<=N; num++) {
			if((int)Math.pow(num,2)>1000000)
				break; //num을 제곱했을 때 범위(100000)를 넘어가면 break
			else {
				for(int i=(int)Math.pow(num, 2); i<=N; i=i+num) {
					arr[i]=1; //num의 배수들은 소수가 아니므로 배열에 1로 저장
				}
			}
		}
		
		for(int i = M; i<=N; i++) {
			if(arr[i]==0) { //소수일 때
				System.out.println(i); //출력
			}
		}

	}

num을 제곱했을 때 범위에 속하면 num의 배수들은 소수가 아니기 때문에 배열에 1로 저장해주면 된다.

두번째 반복문에서 초기값을 int i=(int)Math.pow(num, 2); 로 설정한 이유는 2의 배수를 지우고 3의 배수를 지우면 5의 배수를 지울 때 2의 배수, 3의 배수들 중 이미 지워진 것들이 겹치게 된다.

따라서 중복을 없애기 위해선 제곱한 수부터 배수를 지우면 되기 때문이다!

새로운 개념에 대해 알게된 문제였다.