a121: 質數又來囉

2019-08-12

內容

你的好朋友質數先生又來找你囉，給你兩個數字，請算出這兩個數字包含的範圍內有幾個質數。

輸入

輸入兩個正整數 a,b(1<=a<=b<=100000000)。

保證 b-a<=1000

3 7
6 6
30 50

輸出

輸出一個非負整數，代表 a 到 b 之間(包含 a,b)總共有幾個質數。

3
0
5

解題思路

從開頭試除到結尾，由於任意數不包含自己之最大可能因數為該數的開根號，所以試除時利用該結論簡少不必要的判斷加速。

完整程式碼

AC (0.2s, 88KB)

#include <stdio.h>

int n, m;

int main()
{
    while (scanf("%d %d", &n, &m) == 2)
    {
        int num = 0, i = n;
        for (; i < 2 && i <= m; i++)
            ;
        for (; i <= m; i++)
        {
            num++;
            for (int j = 2; j * j <= i; j++)
            {
                if (i % j == 0)
                {
                    num--;
                    break;
                }
            }
        }
        printf("%d\n", num);
    }
    return 0;
}