C 練習實例33 - 質數(shù)（素數(shù)）判斷

題目：判斷一個數(shù)字是否為質數(shù)。

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

程序源代碼：

實例

// Created by 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=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 %dn", 1, isPrime(1)); printf("N=%d %dn", 2, isPrime(2)); printf("N=%d %dn", 3, isPrime(3)); printf("N=%d %dn", 4, isPrime(4)); printf("N=%d %dn", 7, isPrime(7)); printf("N=%d %dn", 9, isPrime(9)); printf("N=%d %dn", 13, isPrime(13)); printf("N=%d %dn", 17, isPrime(17)); printf("N=%d %dn", 100, isPrime(100)); printf("N=%d %dn", 23, isPrime(23)); printf("N=%d %dn", 1, isPrime(1)); return 0; }

以上實例輸出結果為(末尾數(shù)字 1 表示是質數(shù)，0 表示不是質數(shù))：

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 語言經(jīng)典100例

其他擴展

上一篇：C 練習實例32 下一篇：C 練習實例34