구현

[알고리즘] 소수 알고리즘(에스토스테네스 체)

에스토스테네스 체 -> 소수를 구할 때 사용하는 가장 최적화된 알고리즘이다. 알고리즘 설명 1 ) 먼저 일차원 배열을 하나 만든다. 2 ) Ch[i] == 0이면 ch[i] = 1로 바꾸고 ch[i]의 배수도 모두 1로 바꾼다. Ex ) i = 2일 때, ch[2] == 0이다. 따라서 값을 1로 바꾸고 2의 배수인 4,6,8,10,12,14도 1로 바꾼다. i = 3일 때, ch[3] == 0이다. 따라서 값을 1로 바꾸고 3의 배수인 6,9,12도 값을 1로 바꾼다. i = 4일 때, ch[4] == 1이다. 즉 소수가 아니다. 따라서 그냥 넘어간다. 구현 코드 구현은 다음과 같다.(자바) int cnt=0; int[] ch = new int[n+1]; for(int i=2; i