티스토리 뷰
[문제] 자연수 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값을 올려주면 끝!
이와 같이 소수를 걸러내는 방법을 에라토스테네스 체라고 부른다.
풀이 코드
