백준/에라토스테네스의 체
-
6588 골드바흐의 추측백준/에라토스테네스의 체 2022. 6. 19. 15:25
1. 풀이 에라토스테네스의 체 알고리즘에 대해 먼저 설명하겠다. 소수를 판별하는 알고리즘이다. 만약 20까지의 숫자에 대해서 소수를 판별해보자면 다음과 같다. 아래 그림에서 소수만 남겨보도록 하자. 1. 일단 소수는 1보다 큰 양의 정수이므로, 1을 지워준다. 2. 그 후 2를 제외한 2의 배수를 지워준다. 3. 이번에는 3을 제외하고 3의 배수를 지워준다. 4. 4는 이미 2의 배수로 지워졌기 때문에 5로 넘어간다. 5. 5를 제외하고 5의 배수를 지워준다. 5를 제외한 5의 배수도 2와 3의 배수 때 지워져서 아래처럼 그대로이다. 이런 식으로 지워나가면 된다. 코드에 보면 number 배열이 있는데, 소수이면 true 가 표시된다. 즉, 위의 과정에서 최종 남은 숫자들은 number 배열 값이 tru..