C 练习实例33 - 质数（素数）判断
C 语言教程
· 2019-02-21 20:12:47
题目：判断一个数字是否为质数。
程序分析：质数（prime number）又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数整除。
程序源代码：
实例
// Created by www.codercto.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=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 语言教程 文章: https://www.codercto.com/courses/l/17.html
世界因你不同:李开复自传(纪念版)
李开复，范海涛 著作 / 中信出版社 / 2015-7-10 / 39.00
编辑推荐 1.李开复唯一一部描写全面生平事迹的传记：《世界因你不同：李开复自传》书中讲述了家庭教育培育的“天才少年”；学校教育塑造的“创新青年”，走入世界顶级大公司，苹果、微软、谷歌等亲历的风云内幕，岁月30载不懈奋斗、追求事业成功的辉煌历程。 2.娓娓道来、字字珠玑、可读性和故事性皆佳。李开复博士是青少年成长成才的励志偶像，年轻家长、学校教师阅读后也能从中得到感悟和启发。 3.......一起来看看 《世界因你不同:李开复自传(纪念版)》 这本书的介绍吧!
JS 压缩/解压工具
在线压缩/解压 JS 代码
RGB转16进制工具
RGB HEX 互转工具