소수 찾기

 

 

 

2 3 5 7 11 13 17 19 ....

1과 자기 자신만을 약수로 가지는 수를 소수라고 한다.

소수가 아닌 양의 정수를 합성수라고 부른다.

 

소수를 왜 알아야되지.. 싶기도 한데

알고리즘 문제에서 소수를 구하라고 한다.

그리고 수능 수학을 공부할 때도 확률과통계 과목에서 소인수분해를 통해 여러 경우의 수를 찾기도 했고..

 

소수를 구하는 방법을 컴퓨터에게 어떻게 설명할 지 알아보자.

 

가장 처음으로 떠오르는 생각으로는 1~N 까지 싹다 나눠보면서 접근하는 방법이다.

코드로 살펴보면

 

	public static boolean primecheck(int number) {
		if (number < 2) {
			return false;
		}
		if (number == 2) {
			return true;
		}
		for (int i = 2; i < number; i++) {
			if (number % i == 0) {
				return false;
			}
		}
		return true;
	}

 

소수이면 true를 소수가 아니면 false를 리턴하도록 했다.

좀 무식한 방법이지만 이렇게 풀어줄 수 있다.

 

이렇게 풀어도 되긴 하지만.. 시간 제한이 촉박한 문제들은 이 방법으로 풀리지 않을 수 있다.

좀 더 효율적인 방법이 없을까?

 

에라토스테네스의 체를 사용해 해결할 수 있다.

이 방법으로 N 이하의 모든 소수를 빠르게 구할 수 있다.

 

입력받은 수를 N 이라고 하면, i = 2 부터 root N 이하까지 반복하며 i를 제외한 i의 배수들을 제거하는 방법이다.

 

코드를 통해 살펴보자.

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		
		boolean[] primecheck = new boolean[N + 1];

		if (N < 2) {
			return;
		}

		primecheck[0] = primecheck[1] = true;

		for (int i = 2; i <= Math.sqrt(N); i++) {
			if (primecheck[i] == true) {
				continue;
			}
			for (int j = i * i; j < primecheck.length; j = j + i) {
				primecheck[j] = true;
			}
		}

		for (int i = 0; i < primecheck.length; i++) {
			if (primecheck[i] == false) { 
				System.out.println(i);
			}
		}
	}
}

 

0과 1은 소수가 아니기에 true로 처리해줬다.

소수이면 false, 소수가 아니면 true로 설정했다.

작업의 효율성을 위해 true인 항목이 i 로 들어왔으면 continue로 다음 변수로 넘어가게 했다.