소수의 개수

15. 소수의 개수

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

제한시간은 1초입니다.

 

▣ 입력설명

첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

 

▣ 출력설명

첫 줄에 소수의 개수를 출력합니다.

 

▣ 입력예제 1

20

 

▣ 출력예제 1

8

 

// 소수의갯수를 1초안에 구하는 문제 n^2을 이용하면 턱없이 부족함 주어진 숫자의 제곱근까지만 확인하면 되는 성질을 이용함

 

<코드>

#include <iostream>

using namespace std;

int main()
{
    int in, cnt = 0;
    bool flag;
    cin >> in;

    for (int i = 2; i <= in; i++)
    {
        flag = true;
        for (int j = 2; j * j <= i; j++)
        {

            if (i % j == 0)
            {
                flag = false;
                break;
            }
        }
        if (flag)
            cnt++;
    }

    cout << cnt;
}