[JAVA] 알고리즘 문제 - 소수(에라토스테네스 체)

소수

1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수. 

 

설명

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

 

입력

첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

 

출력

첫 줄에 소수의 개수를 출력합니다.

 

입력예시

20

출력예시

8

 

import java.util.Scanner;

public class Main {
 
	public int test(int n) {
		int answer = 0;
		int[] ch = new int[n+1];
		
		for(int i=2; i<=n; i++) {
			if(ch[i] == 0) {
				answer++;
				for(int j=i; j<=n; j=j+i) {
					ch[j]=1;
				}
			}
		}
		return answer;

	}
	
	public static void main(String[] args){
		Main t = new Main();
		Scanner kb = new Scanner(System.in);
		
		int n = kb.nextInt();
		
		System.out.println(t.test(n));
    }
}

 

첫번째로 자연수를 입력받으면 해당 1부터 해당 자연수까지의 숫자중에서 소수의 갯수를 출력한다.

20을 입력 받는다면 2, 3, 5, 7, 11, 13, 17, 19 => 총 8개의 소수가 있다.

 

에라토스테네스 체

고대의 그리수 수학자가 만들어 낸 소수를 구하는 방법이다.

 

0과 1은 해당사항이 없기 때문에 i=2부터 시작한다. 그리고 여기서 배열의 길이는 입력받은 숫자의 +1을 해줘야한다.

만약 11을 입력받은 경우이다. 따로 값을 지정하지 않았기에 맨처음에는 0으로 모두 초기화된다.  

2	3	4	5	6	7	8	9	10	11
0	0	0	0	0	0	0	0	0	0

이제 for문을 도는데 값이 0인경우 answer++ 를 통해 소수를 체크한다.

그리고 0인경우에 다시 for문을 돌며 i의 배수에 해당되는 배열 index의 값을 모두 1로 변경한다.

 

2	3	4	5	6	7	8	9	10	11
1	0	1	0	1	0	1	0	1	0

i=2인경우 이와같이 배열의 값들이 변경된다. 그리곤 3의 위치에서 값이 0이므로 1로 변경 후 배수들을 모두 1로 변경

 

2	3	4	5	6	7	8	9	10	11
1	1	1	0	1	0	1	1	1	0

이와 같이 반복한다면 소수만을 체크하고 배열탐색이 모두 종료된다.

 

11을 입력 받았다면 2, 3, 5, 7, 11 총 5개의 소수가 있는 것을 확인이 가능하다.