[C] 判斷是否為質數以及質數的數量

質數是指除了有1和自身作為約數外，不再有其他約數的數

若要確定某數是否為質數，除了可以除以所有比自己小的數來判斷是否為質數，我們可以加快只除以一半的數來判斷。而中間的因數怎麼算出來呢?絕對不是直接除以二，而是開根號。舉例來說，64因數為1,2,4,8,16,32,64，中間的因數為8，即64的開根號。基於這樣的想法，C code如下

int is_prime(int a){
    if(a == 1 || a == 0)
        return 0;
    for(int i=2; i*i<=a; i++){
        if(a % i == 0)
            return 0;
    }
    return 1;
}

若要知道一個非零整數比它小的質數有幾個

C code solution:

int is_prime(int a){
    if(a == 1 || a == 0)
        return 0;
    for(int i=2; i*i<=a; i++){
        if(a % i == 0)
            return 0;
    }
    return 1;
}
int how_many_prime(int a){
    int res = 0;
    for(int i=2; i<=a; i++){
        if(is_prime(i))
            res++;
    }
    return res;
}
int main() {
    printf("%d\n", is_prime(97));
    printf("%d", how_many_prime(100));
    return 0;
}

output:

1
25