###### tags: `實習題目` `大一程設` `東華大學` `東華大學資管系` `基本程式概念` `資管經驗分享`

質數判斷進階版
===

## Description
請輸入一個數，你的程式會輸出在這個數之前(包含這個數)有多少個質數。

## Constraint
* 禁止使用迴圈完全遍歷，因為這樣會跑非常多次，大概會跑 $n^2$ 次，是非常沒有效率的，請優化你的算法。
* tips : 不要說對你們不好，看看[參考連結](https://kknews.cc/zh-tw/code/25x4xoe.html)吧，裡面是用 python 解的，但希望你們把解題思維學起來，用 C++ 寫出來

### 甚麼是完全遍歷?
我下面寫的叫做 pseudo code，不是任何程式語言的語法，只是為了方便說明我想表達的事，以後演算法國暉會很常寫這樣的東西哦~大家可以體驗看看

    //假設你輸入 10 這個數
    for i from 2 to 10
        for j from 2 to i
        // 裡面在做質數判斷~

上面這樣就叫做完全遍歷，輸入10這個數表示想知道10之前有幾個質數，而針對10之前的每個數，我們都從2跑到當前的數 $i$ ，一個一個判斷能不能整除掉當前的 $i$ (外層迴圈)，但這樣很沒效率，希望你們用比較有效率的方式。

## Sample Input & Output 1

5
3

## Sample Input & Output 2

16
6

## Sample Input & Output 3

55
16