에라토스테네스의 체 cpp

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

소수를 찾는 방법 중 에라토스테네스의 체 방법을 설명드리겠습니다. 시간복잡도: O(NloglogN) 에라토스테네스의 체 원리 1. 2부터 120(예시)까지 모든 숫자를 나열합니다. (1은 소수가 아니므로) 2. 숫자 하나씩 방문하면서 자기자신을 제외한 배수를 제거합니다. (2를 방문했다면 2를 제외한 배수 4부터 지우기) 3. bool함수를 이용해 전에 지웠던 숫자를 다시 방문하지 않게 합니다. 소수만 출력하는 코드 #include const int INF = 10001; int arr[INF]; bool primearray[INF]; void Eratos(int n) { if (n