알고리즘 연습 - 소수 찾기 - JAVA (에라토스테네스의 체 알고리즘)

문제

에라토스테네스의 체

출처:위키백과

에라토스테네스의 체는 소수를 찾는 방식입니다

1.2부터 자신이 찾고자하는 범위의 수들을 전부 나열합니다.

2. 이후에 10이전의 소수들을 자신을 제외한 배수들을 제외합니다.(2,3,5,7)

3. 지우고나면 지워지지않은 수들이 남는데 이 수들이 소수입니다.

- 에라토스테네스의 체 알고리즘을 사용했을때 프로그램이 소수를 찾는데 시간이 확 줄일 수 있습니다.

문제해석

1. n+1번째 까지의 boolean타입의 빈배열을 만들어 줍니다. (초기값은 false)

2. 2의 배수, 3의 배수, 5의 배수, 7의 배수를 자신을 제외한 수를 true로 바꾸어 줍니다. 

3. false에서 true값으로 변하면 count를 하나 올려줍니다.

코드

import java.util.*;
class Solution{
    public int solution(int n) {
        boolean[] b = new boolean[n+1];
        int count = 0;
        for(int i=2;i<=n;i++) {
            if(b[i] == false) {
                count +=1;
                for(int j=i;j<=n;j+=i) {
                    b[j] = true;                
                }
            }            
        }        
        return count;
    }
}
public class Prime {
 
    public static void main(String[] args) {
        Solution ss = new Solution();
        System.out.println(ss.solution(10000000));
        
    }
 
}
 

여기서 이미 배수로 지워진 부분은 true값으로 변했기 때문에 count가 되지않습니다.

HyunInKim/algorithm

Contribute to HyunInKim/algorithm development by creating an account on GitHub.

github.com