프로그래머 LV1 C++ 문제) 소수 찾기

문제 설명

1과 입력한 숫자 n 사이의 소수의 수를 반환하는 함수 솔루션을 만듭니다.

소수는 1과 자기 자신으로만 나누어지는 수입니다. (1은 소수가 아닙니다.)

강제

• n은 2 이상 1,000,000 이하의 자연수이다.

입력 및 출력 예

결과

I/O 예시 설명

I/O 예제 # 11과 10 사이에 4개의 소수(2,3,5,7)가 있으므로 4를 반환합니다.

I/O 예제 #21 ~ 5는 3개의 소수(2,3,5)가 있으므로 3을 반환합니다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    
    for(int i=2;i<=n;i++)
    { bool is_prime= true;
        for(int k=2;k*k<=i;k++) //절반까지만 탐색해도 된다.
        {
            if(i%k==0)
            {
                is_prime=false;
                break;
            }

        }
        if(is_prime)
        {
            answer++;
        }
    }
    return answer;
}