C 練習實例33 - 質數（素數）判斷

C 語言經典100例 C 語言經典100例

題目：判斷一個數字是否為質數。

程式分析：質數（prime number）又稱素數，有無限個。一個大於1的自然數，除了1和它本身外，不能被其他自然數整除。

程式源代碼：

實例

// Created by www.xuhuhu.com on 15/11/9. // // #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=i+2) { if(n % i == 0) return 0; } return 1; } void sieve() { prime[0] = 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) { if(prime[n]) return 1; else return 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; }

以上實例輸出結果為(末尾數字 1 表示是質素，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

C 語言經典100例 C 語言經典100例