[C++] 소수 찾기(연습문제)

문제는 간단하다 1부터 입력받은 숫자 n까지 중 소수가 몇 개 있는지 반환하면 된다.

n이 10이라면 1부터 10에는 2, 3, 5, 7 총 4개의 소수가 존재하므로 4를 반환하고 5라면 2, 3, 5 총 3개의 소수가 존재하므로 3을 반환한다.

 

설계 및 구현

구현을 위해 주어진 함수는 반환 타입으로 int를 가지고 매개변수 int타입의 n을 가지는 함수이다. 구현의 내용은 파이썬과 마찬가지로 에라토스테네스의 체를 사용하면 된다. 구현 내용은 파이썬과 같으므로 정리하면

① n까지의 모든 숫자 나열

② 2의 배수, 3의 배수 ... 남은 소수들의 배수 모두 지우기

 

①을 수행하기 위해 소수판별을 위한 숫자를 벡터에 넣는 것이 아닌 인덱스로 사용한다. 벡터에 n+1의 개수만큼 True로 만든다. 1부터가 아닌 2부터로 판단할 것이므로 n+1개만큼 만들어낸다.

②의 수행 과정으로 반복문을 n의 제곱근만큼만 수행한다. 이유는 배수를 지워내는데 최대 크기인 n의 약수중 가장 큰 수는 n의 제곱근이기 때문에 n까지 전부 확인할 필요가 없기 때문이다. 반복을 수행하며 배수들의 인덱스에는 소수가 아니기 때문에 True대신 False를 삽입한다. 그리고 2부터 인덱스를 사용하여 True인 경우에만 개수를 세면 소수의 개수가 나오게 된다.

 

위의 코드를 통해 채점을 통과할 수 있었다.