JAVA 소수 구하기 - 에라토스테네스의 체

소수란, '1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수' 

에라토스테네스의 체 란 수학에서 에라토스테네스의 체는 소수를 찾는 방법으로 고대 그리스 수학자 에라토스테네스가 발견하였다.그 방법으로 소수를 구하는 알고리즘 풀이를 하겠습니다.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

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

---

n개의 수를 입력받습니다.

n이 10이라면, 0 1 2 3 4 5 6 7 8 9 10 까지의 수 중 소수의 개수를 구하는 문제입니다

즉, 결과는 2,3,4,7 이 소수이니 4가 결과 값으로 출력되야 합니다.

 

import java.util.Scanner;

public class Main {

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

---

풀이

배열을 사용할 것 입니다.

n에 10이라는 수가 주어진다면 0~10 까지의 수를 구해야 합니다.

배열은 0부터니 10까지 구하려면 n+1개의 배열을 만들어주어야 합니다.

그래서 n+1개인 11의 크기를 가지는 배열을 만들어 줍니다. 0으로 모두 초기화 되있는 상태입니다.

그러면 0 1 2 3 4 5 6 7 8 9 10 에 모두 0이 들어가있겠죠?

 

소수는 1보다 큰 자연수여야 합니다.

그러니 0과1은 제외 됩니다.

그래서 2부터 10까지를 구하면 됩니다.

 

2부터 시작해보겠습니다. 2는 소수이니 result 값을 1 더해줍니다.

그 후 2의 배수의 인덱스를 가진 수를 1로 바꿔줍니다.

그러면 2, 4, 6, 8 ,10 의 인덱스의 값들이 1로 바뀝니다.

 

다음 3으로 갑니다. 3도 현재의 값이 0 이니 result 에 1 더해줍니다.

그러고 3의 배수를 찾습니다. 3, 6, 9 를 1로 만들어줍니다.

 

그렇게 10까지 반복하게 되면 0인 경우만 소수가 되겠죠.

이미 0인 수들만 더해왔기에 result를 출력하면 됩니다.

 

---

2 3 4 5 6 7 8 9 10

0 0 1 0 1 0 1 1 1