에라토스테네스 체
[문제] 자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다. 0으로 초기화된 int배열을 가지고 for문을 돌면서, 각 index(자연수)의 배수를 1로 체크해준다. → 1로 체크된 index(자연수)는 1과 자신으로만 나누어지는 것이 아니므로 소수가 아니기 때문에! 앞선 반복문에서 1로 체크되지 않았다면 소수가 맞기때문에 answer값을 올려주면 끝! 이와 같이 소수를 걸러내는 방법을 에라토스테네스 체라고 부른다. 풀이 코드
algorithm
2022. 4. 27. 14:24
