淘宝双十一超级红包 》
C 练习实例33 - 质数（素数）判断
C 语言经典100例题目：判断一个数字是否为质数。
程序分析：质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除。
程序源代码：
实例
#include<stdio.h>
#include<math.h>
#define MAX 1000 // 最大数组大小
int prime[MAX]; // 存储是否为质数的数组
// 判断数字是否为质数的简单方法（暴力法）
int isPrimeNaive(int n)
{
if (n <= 1) // 1及以下的数字不是质数
return 0;
for (int i = 2; i < n; i++) // 从2到n-1逐一检查是否能整除n
if (n % i == 0) // 如果能整除，则不是质数
return 0;
return 1; // 找不到因数，则是质数
}
// 优化后的质数判断方法：只检查到sqrt(n)，并跳过偶数
int isPrime(int n)
{
if (n <= 1) // 1及以下的数字不是质数
return 0;
if (n == 2) // 2是质数
return 1;
if (n % 2 == 0) // 排除偶数
return 0;
int limit = (int)sqrt((double)n); // 只需要检查到sqrt(n)
for (int i = 3; i <= limit; i += 2) // 从3开始，只检查奇数
{
if (n % i == 0) // 如果能整除，则不是质数
return 0;
}
return 1; // 通过所有测试，n是质数
}
// 筛法初始化质数表
void sieve()
{
for (int i = 0; i < MAX; i++)
prime[i] = 1; // 假设所有数都是质数
prime[0] = prime[1] = 0; // 0和1不是质数
int limit = (int)sqrt((double)MAX); // 只需要检查到sqrt(MAX)
for (int i = 2; i <= limit; i++) // 从2开始，遍历每个数字
{
if (prime[i]) // 如果i是质数
{
for (int j = i * i; j < MAX; j += i) // 标记i的倍数为非质数
prime[j] = 0;
}
}
}
// 通过筛法判断一个数是否为质数
int isPrimeSieve(int n)
{
return prime[n]; // 直接返回该位置是否为质数
}
int main()
{
sieve(); // 初始化质数筛选
// 测试各种数字是否为质数
printf("N=%d %d\n", 1, isPrime(1)); // 输出：1 不是质数
printf("N=%d %d\n", 2, isPrime(2)); // 输出：2 是质数
printf("N=%d %d\n", 3, isPrime(3)); // 输出：3 是质数
printf("N=%d %d\n", 4, isPrime(4)); // 输出：4 不是质数
printf("N=%d %d\n", 7, isPrime(7)); // 输出：7 是质数
printf("N=%d %d\n", 9, isPrime(9)); // 输出：9 不是质数
printf("N=%d %d\n", 13, isPrime(13)); // 输出：13 是质数
printf("N=%d %d\n", 17, isPrime(17)); // 输出：17 是质数
printf("N=%d %d\n", 100, isPrime(100)); // 输出：100 不是质数
printf("N=%d %d\n", 23, isPrime(23)); // 输出：23 是质数
printf("N=%d %d\n", 1, isPrime(1)); // 输出：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