에라토스테네스의 체

[baekjoon 1978] 소수 찾기- 소수, 에라토스테네스의 체 (C++)

www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 소수 판정 알고리즘인 에라토스테네스의 체를 이용해서 풀었다. - 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. (baekjoon 2960 에라토스테네스의 체 문제에서 참고) 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. 따라서 소수 P를 찾은..