C语言经典例题100例——C语言练习实例33解答(质数<素数>判断)

作者(出处):百宝箱工作室发布时间:2017年8月1日 21:05:09查阅量:176

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

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

程序源代码:

// 百宝箱工作室  官方网址 http://www.baibaox.com
// 百宝箱工作室业务介绍 http://www.baibaox.com/BusinessIntroduction.html

#include<stdio.h>
#include<math.h>
#define MAX 1000

int prime[MAX];

int isPrimeNaive(int n)
{
    int i;
    if(n <= 1)
        return 0;
    for(i = 2; i < n; i++)
        if(n % i == 0)
            return 0;
    return 1;
}
 
int isPrime(int n)
{
    int i;
    int limit;
    if(n<= 1)
        return 0;
    if(n == 2)
        return 1;
    if(n%2 == 0)
        return 0;
    limit = (int)sqrt((double)n);
    for(i = 3; i <= limit; i=i+2)
    {
        if(n % i == 0)
            return 0;
    }
    return 1;
}
 
void sieve()
{
    int i;
    int j;
    int limit;
    prime[0] = 0;
    prime[1] = 0;
    for(i = 2; i < MAX; i++)
        prime[i] = 1;
    limit = (int)sqrt((double)MAX);
    for(i = 2; i <= limit; i++)
    {
        if(prime[i])
            for(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;
}

以上实例运行结果如下:

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
百宝箱网络工作室  版权所有  
站长QQ:1617818397  站长E-mail:1617818397@qq.com
Powered by www.baibaox.com  Copyright © 2011-2017
点击这里给我发消息