C語言練習實例33：素數判斷多種算法對比

本實例實現三種素數判斷函數：朴素法、優化試除法、埃拉托斯特尼篩法預計算。

三種方法

• isPrimeNaive：試除 2 到 n-1，O(n)。
• isPrime：排除偶數，試除 3 到 sqrt(n) 步長 2，O(√n)。
• sieve + isPrimeSieve：預計算 MAX 以內素數表，查詢 O(1)，適合多次查詢。

源代碼

// Created by www.runoob.com on 15/11/9.
// Copyright © 2015年 菜鳥教程. All rights reserved.
//
#include <stdio.h>
#include <math.h>
#define MAX 1000

int prime[MAX];

int isPrimeNaive(int n) {
    if (n <= 1) return 0;
    for (int i = 2; i < n; i++)
        if (n % i == 0) return 0;
    return 1;
}

int isPrime(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    int limit = (int)sqrt((double)n);
    for (int i = 3; i <= limit; i += 2)
        if (n % i == 0) return 0;
    return 1;
}

void sieve() {
    prime[0] = prime[1] = 0;
    for (int i = 2; i < MAX; i++) prime[i] = 1;
    int limit = (int)sqrt((double)MAX);
    for (int i = 2; i <= limit; i++)
        if (prime[i])
            for (int j = i*i; j <= MAX; j += i)
                prime[j] = 0;
}

int isPrimeSieve(int n) {
    return prime[n] ? 1 : 0;
}

int main() {
    sieve();
    printf("N=%d %d\n", 1, isPrime(1));
    printf("N=%d %d\n", 2, isPrime(2));
    printf("N=%d %d\n", 3, isPrime(3));
    printf("N=%d %d\n", 4, isPrime(4));
    printf("N=%d %d\n", 7, isPrime(7));
    printf("N=%d %d\n", 9, isPrime(9));
    printf("N=%d %d\n", 13, isPrime(13));
    printf("N=%d %d\n", 17, isPrime(17));
    printf("N=%d %d\n", 100, isPrime(100));
    printf("N=%d %d\n", 23, isPrime(23));
    printf("N=%d %d\n", 1, isPrime(1));
    return 0;
}

運行結果

N=1 0
N=2 1
N=3 1
N=4 0
N=7 1
N=9 0
N=13 1
N=17 1
N=100 0
N=23 1
N=1 0

末尾 1 表示素數，0 表示合數。