[백준 알고리즘][자바] 1929번 : 소수 구하기와 소수(Prime Number) 판별법 알고리즘

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

이번 포스팅은 백준 알고리즘 1929번 소수 구하기입니다.

주어진 입력인 자연수 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하는 문제입니다. 

같은 맥락으로 전에 소수와 관련된 문제는 1978번이 있었습니다.

2021.08.02 - [Algorithm/Baekjoon] - [백준 알고리즘][자바] 1978번 : 소수 찾기

[백준 알고리즘][자바] 1978번 : 소수 찾기

1978번에서는 특별한 알고리즘 없이 소수(Prime Number)의 정의 그대로

1부터 주어진 자연수 N까지 나누어지는 수를 카운팅 하여 소수를 판별했습니다.
이번 문제에도 그대로 적용하여 아래와 같은 코드를 작성하였습니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String numArr[] = br.readLine().split(" ");
		int A = Integer.parseInt(numArr[0]);
		int B = Integer.parseInt(numArr[1]);
		
		for(int i = A ; i <= B ; i++) {
			int count = 0;
			if(i == 1) {
				continue;
			}else {
				for(int i2 = 1 ; i2 <= i ; i2++) {
					if(i % i2 == 0) {
						count++;
					}
					
					if(count > 2) {
						break;
					}
				}
				
				if(count == 2) {
					bw.write(String.valueOf(i + "\n"));
				}
			}
		}

		br.close();
		bw.flush();
		bw.close();
	}
}

위와 같이 시간 초과가 되었습니다.

더욱 빠른 시간복잡도를 위한 소수(Prime Number) 판별법 알고리즘을 소개합니다.

 

 

제곱근을 이용한 소수 판별법

소수(Prime Number)의 정의는 1과 자기 자신만을 약수로 가지는 자연수입니다.

예를 들어 자연수 12는 1, 2, 3, 4, 6, 12를 약수로 가지고 있습니다.

(2-6), (3-4), (4-3), (6-2)는 서로 자리만 바뀌면 결국 같다고 할 수 있습니다.

이들의 관계 중 작은 쪽인 2, 3은 모두 자연수 N의 제곱근보다 작은 범위에 존재합니다.

따라서 자연수 N의 약수의 개수를 구할 때, 1부터 sqrt(N)까지만 체크하여 약수의 개수가 1개라면(1의 경우)
그 수는 소수가 되는 것입니다.

 

public static boolean check(int num) {
		if(num == 1) {
			return false;
		}
		
		if(num == 2) {
			return true;
		}
		
		for(int i = 2 ; i <= (int)Math.sqrt(num) ; i++) {
			if(num % i == 0) {
				return false;
			}
		}
		
		return true;
	}

 

에라토스테네스의 체

1의 자리에서 소수인 2, 3, 5 7의 배수는 약수로 무조건 2, 3, 5, 7을 포함하기 때문에 소수가 될 수 없다.라는 정의를 이용하여 소수의 배수인 자연수들을 제외하게 되면 소수만 남게 됩니다.

체를 이용하여 소수가 아닌 수들을 걸러내는 방식이라고 생각하면 됩니다.

 

public class Eratos {
	public static void main(String[] args) {
		// ArrayList로 구현
		ArrayList<Boolean> primeList;

		// 사용자로부터의 콘솔 입력
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		// n <= 1 일 때 종료
		if(n <= 1) return;

		// n+1만큼 할당
		primeList = new ArrayList<Boolean>(n+1);
		// 0번째와 1번째를 소수 아님으로 처리
		primeList.add(false);
		primeList.add(false);
		// 2~ n 까지 소수로 설정
		for(int i=2; i<=n; i++ )
			primeList.add(i, true);

		// 2 부터  ~ i*i <= n
		// 각각의 배수들을 지워간다.
		for(int i=2; (i*i)<=n; i++){
			if(primeList.get(i)){
				for(int j = i*i; j<=n; j+=i) primeList.set(j, false);
				//i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다.
			}
		}
		StringBuffer sb = new StringBuffer();
		sb.append("{");
		for(int i=0; i<=n; i++){
			if(primeList.get(i) == true){
				sb.append(i);
				sb.append(",");
			}
		}
		sb.setCharAt(sb.length()-1, '}');

		System.out.println(sb.toString());

	}
}

출처 : 나무위키

 

위의 두 가지 알고리즘을 이용하여 1929번 : 소수 구하기를 해결할 수 있습니다.

저는 제곱근 방식을 이용하여 아래와 같은 코드를 짰습니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String numArr[] = br.readLine().split(" ");
		int A = Integer.parseInt(numArr[0]);
		int B = Integer.parseInt(numArr[1]);
		
		for(int i = A ; i <= B ; i++) {
			if(check(i)) {
				bw.write(String.valueOf(i + "\n"));
			}else {
				continue;
			}
		}

		br.close();
		bw.flush();
		bw.close();
	}
	
	public static boolean check(int num) {
		if(num == 1) {
			return false;
		}
		
		if(num == 2) {
			return true;
		}
		
		for(int i = 2 ; i <= (int)Math.sqrt(num) ; i++) {
			if(num % i == 0) {
				return false;
			}
		}
		
		return true;
	}
}