判斷一個(gè)數(shù)是否為質(zhì)數(shù)

int is_prime(int n) {
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return 0; // 不是質(zhì)數(shù)
        }
    }
    return 1; // 是質(zhì)數(shù)
}

素?cái)?shù)篩選法（時(shí)間復(fù)雜度O(nlogn)）

for (int i = 2; i <= n; ++i) {
    is_prime[i] = 1;
}
for (int i = 2; i <= n; ++i) {
    for (int j = i * 2; j <= n; j += i) {
        is_prime[j] = 0;
    }
}

for (int i = 2; i <= n; ++i) {
    is_prime[i] = 1;
}
for (int i = 2; i * i <= n; ++i) {
    if (is_prime[i]) {
        for (int j = i * i; j <= n; j += i) {
            is_prime[j] = 0;
        }
    }
}