C語言實(shí)現(xiàn)統(tǒng)計100以內(nèi)所有素數(shù)的個數(shù)

更新時間：2021年11月26日 09:36:46 作者：小輝_Super

本文詳細(xì)講解了C語言實(shí)現(xiàn)統(tǒng)計100以內(nèi)所有素數(shù)個數(shù)的方法，文中通過示例代碼介紹的非常詳細(xì)。需要的朋友可以收藏下，方便下次瀏覽觀看

題目描述

統(tǒng)計100以內(nèi)所有素數(shù)的個數(shù)

分析

素數(shù)（prime number）又稱質(zhì)數(shù)，在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)的數(shù)稱為質(zhì)數(shù)，2是最小的素數(shù)。

代碼實(shí)現(xiàn)

#include <stdio.h>

#define INTEGER_RANGE 100  //數(shù)字范圍

int if_prime(int num);

int main()
{
    int sum = 0;
    /* 2是最小的素數(shù)，for循環(huán)范圍為2-100 */
    for(int i = 2; i <= INTEGER_RANGE; i++)
    {
        if(if_prime(i))
            sum++;
    }
    printf("%d以內(nèi)的素數(shù)個數(shù)為：%d\n", INTEGER_RANGE, sum);
    return 0;
}

/*
 * 判斷是否為素數(shù)，是則返回1，否返回0
 * */
int if_prime(int num)
{
    int i = 0;
    for(i = 2; i < num; i++)
    {
        /* 如果該數(shù)有存在1以外的其他正因數(shù)，則不是素數(shù) */
        if(num % i == 0)
            return 0;
    }
    return 1;
}

運(yùn)行結(jié)果

后期完善

這里只對if_prime(num)函數(shù)進(jìn)行完善：

增加非法數(shù)字的判斷，num小于2直接返回0
將循環(huán)范圍由2~num-1改成2~sqrt(num)

至于為什么用sqrt,這里借用下別人的解釋（比較通俗易懂）

當(dāng)一個數(shù)不是素數(shù)的時候，那這數(shù)肯定是除了它本身和1外的兩個數(shù)之積（ a*b = m ),如果設(shè) a是小于或者等于 b的數(shù)，那 a肯定是小于等于 m的開根，即 a <= sqrt( m ) ?！俣荣N吧（C語言吧）

還有一種用法是把num改成num/2，但是當(dāng)num大于4時，sqrt(num)比num/2小，所以用sqrt(num)的效率比用num/2高。
至于為什么可以用num/2，這里也借用別人的解釋（有點(diǎn)難懂）

其實(shí)這是數(shù)學(xué)知識，n不除以2也行，只是運(yùn)算量更大，其實(shí)最少運(yùn)算量的方法是n開根號。
我證明一下合理性吧。用反證法。
如果一個數(shù)是合數(shù)，則一定能分解成兩個不是1的數(shù)相乘，所以能被分解成一個大于等于2的數(shù)和一個小于等于n/2相乘。
如果這個數(shù)沒有一個小于等于n/2的因數(shù)，那它一定不是合數(shù)，所以它一定是素數(shù)，不用再檢查后面的數(shù)了。這里是小于n/2，是因為如果這個數(shù)能被n/2整除，那2一定是它的因數(shù)，很容易知道2小于等于n/2，所以在檢查n/2之前一定檢查過2。證明完成！
n開根號也差不多這樣證明?！?a rel="external nofollow" target="_blank">https://fishc.com.cn/thread-181309-1-1.html

如果你對上面的兩種用法都不理解，那記住它們就行了。。。

#include <math.h>
/*
 * 判斷是否為素數(shù)，是則返回1，否返回0（改進(jìn)版）
 * */
int if_prime(int num)
{
    if(num < 2)
        return 0; //最小的素數(shù)為2
    int i = 0;
    //sqrt():開方函數(shù)（一定要寫小于等于）
    for(i = 2; i <= sqrt(num); i++)
    {
        /* 如果該數(shù)有存在1以外的其他正因數(shù)，則不是素數(shù) */
        if(num % i == 0)
            return 0;
    }
    return 1;
}

網(wǎng)上參考

原文鏈接：https://www.runoob.com/cprogramming/c-exercise-example36.html
sqrt()為開方函數(shù)，需要加math.h頭文件

//  Created by www.runoob.com on 15/11/9.
//  Copyright ? 2015年 菜鳥教程. All rights reserved.
//
 
#include<stdio.h>
#include<math.h>
int main()
{
    int i,j,k,n=0;
    for(i=2;i<=100;i++)
    {
        k=(int)sqrt(i);
        for(j=2;j<=k;j++)
            if(i%j==0) break;
        if(j>k)
        {
            printf("%d ",i);
            n++;
            if(n%5==0)
                printf("\n");
        }
    }
    return 0;
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: