에라토스테네스 체 (소수 구하기)
2부터 자기 자신을 제외하고 배수를 모두 지우면 남은 수가 소수가 되는 알고리즘.
- 준비 : boolean[] arr = new boolean[n + 1] --> 어떤 수의 배수인지 아닌지 표시할 배열
문제
1부터 N까지 소수의 개수를 출력하는 프로그램
가장 바깥쪽 반복문에 루트를 씌우는 이유 : 예를 들어 N이 30일 때, i가 2일 때, 2,4,6,8,,,30까지 true로 표시되고, i가 3일 때, 3,6,9,,,27까지 true로 표시되고 i가 4일 때, 4,8,12,,,28까지 true로 표시.. 이런식으로 가다가 i가 6이 되면
6은 2 X 3으로 구성된 수이기 때문에, 6의 배수는 이미 앞에서 2와 3의 배수로 탐색되어 true로 표시되었다.
7은 소수이고 8도 2 X 2 X 2로 구성된 수이기 때문에 8의 배수는 앞에서 2의 배수로 탐색되었다. 10은 2 X 5로 구성된 수이기 때문에 10의 배수는 앞에서 2 와 5의 배수로 이미 탐색되었다.
Record What I Learned