Bailian3177 判決素數個數【入門】（POJ NOI0113-10）

問題連結：POJ NOI0113-10 判決素數個數。

判決素數個數

總時間限制:  

1000ms  

記憶體限制:  

65536kB

描述

輸入兩個整數X和Y，輸出兩者之間的素數個數（包括X和Y）。

輸入

兩個整數X和Y（1 <= X,Y <= 10 5）。

輸出

輸出一個整數，表示X，Y之間的素數個數（包括X和Y）。

樣例輸入

1 100      

樣例輸出

25      

問題連結：Bailian3177 判決素數個數

問題分析：（略）

程式說明：題意沒有說x和y哪個大，還是比較交換一下比較放心。單獨考慮偶數可以使得判定素數的程式做得更加快一些。

題記：把功能封裝到函數中是一種好的做法。

　

AC的C語言程式如下：

/* Bailian3177 判決素數個數 */

#include <stdio.h>

void swap(int *a, int *b)
{
    int t;

    t = *a;
    *a = *b;
    *b = t;
}

int isprime(int n)
{
    int i;

    for(i=3; i*i<=n; i+=2)
        if(n % i == 0)
            return 0;

    return 1;
}

int main(void)
{
    int x, y, sum=0, i;

    scanf("%d%d", &x, &y);

    if(x > y)
        swap(&x, &y);
    if(x <= 2) {
        x = 3;
        sum = 1;
    } else {
        if(x % 2 == 0)
            x++;
        sum = 0;
    }
    for(i=x; i<=y; i+=2)
        if(isprime(i))
            sum++;

    printf("%d\n", sum);

    return 0;
}