C 练习实例33 _ 质数(素数)判断

C 语言经典100例 C 语言经典100例

题目:判断一个数字是否为质数。

程序分析:质数(prime number)又称素数,有无限个。一个大于1的自然数,除了1和它本身外,不能被其他自然数整除。

程序源代码:

实例

// Created by www.icodebang.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 语言经典100例 C 语言经典100例

0 个评论

要回复文章请先登录注册