Jasin Yip

计蒜客【挑战难题】系列讲解(三)判断质数

题目

第3题:判断质数

  对于大于1的数,如果除了1和它本身,它不能再被其它正整数整除,那么我们说它是一个质数。晓萌想判断一个数是不是质数,希望找你写个程序,帮助她进行判断。
  输入包括一行,为一个整数N(1 < N ≤1000),正是晓萌给出你让你判断的数字。
  输出包括一行,如果晓萌给出的整数N为质数,那么输出YES;如果N不是质数,那么输出NO。

样例输入

3

样例输出

YES

C实现

    #include "stdio.h"  
    #include "math.h"  
    int main(){  
        int Num, i;  
        scanf("%d", &Num);  
        if (Num == 2){
            printf("YES");
            return 0;
        }
        if (Num % 2 == 0){  //先判断是否为偶数,若偶数就直接输出NO并结束程序  
            printf("NO");  
            return 0;   //在主程序main()中使用return 0可以直接结束程序  
        }  
        //从3开始,到Num的算术平方根结束,步进为2 
        for (i = 3; i <= sqrt(Num); i += 2)   
            if (Num % i == 0){  
                printf("NO");  
                return 0;  
            }  
        printf("YES");  
        return 0;  
    }  

它如何工作

根据质数的定义(除1和它本身外不能被其它数整除的数),这个题对于初学者来说有点儿难度,一下子想不到该怎么下手。

算法是怎样来的?

我们可以这样想:如果我们用大脑来判断这个数是不是质数,是该怎样的呢?

比如我拿 4 来举例。
假设我并不知道它能被什么数整除,
那我一个一个试总行了吧?
当然,1不用试,那我从2开始试吧!
于是发现4可以被2整除耶!
那我就可以判定:4这个数不是质数。

嗯……好像还是想不到怎么做。
那就再举个粟子呗~

这次我拿 9 来举例。
我还是先试2,嗯,9不能被2整除。
那我试一试3,嗯,9能被3整除。
那我就可以判定:9这个数不是质数。

再举一个质数的例子:5 。
试2,不能整除。
试3,不能整除。
试4,不能整除。
噢,到了5(它的本身)了,好吧~
我可以宣布一个事实了:5是质数!

说到这儿,大家得到什么启发?
我们可以从2开始,直到n-1,试除每一个数字。
如果都不能整除n,那么n就是质数了!

所以,我们根据上面的分析,想到了用循环去试除2~(N-1)的每一个数。
于是得到以下代码:

    for (i = 2; i <= Num - 1; i ++)   //从2开始,循环至(N-1)结束  
        if (Num % i == 0){  //判断是否能整除  
            printf("NO");  
            return 0; //在主程序main()里使用return 0可使整个程序结束
        }  

好了,这样已经可以实现判断质数的能力了。

那么,我们能不能对其进行优化呢?
答案是肯定的。
首先,如果n是偶数,那就肯定不是质数了(可以输出NO并结束了),因为它能被2整除。
所以,如果n不是偶数的话,我们只需要从3开始,只试除3、5、7这样的奇数就好了。
所以我们可以把循环:写成由3开始,根号Num结束,步进为2的循环。

    //由3开始,根号Num结束,步进为2的循环
    for (i = 3; i <= Num - 1; i += 2)      
        if (Num % i == 0){  
            printf("NO");  
            return 0;  
        }  

这样的程序可以节省一半的循环量,速度已经挺快的了。

最后介绍一个数学知识:我们只需要试除到n的算术平方根,如果都没有能整除它的数,那么就能判断这个数是质数了。
至是为神马我这里不细说,有兴趣可以百度。
最后循环改成这样ok啦:

    for (i = 3; i <= sqrt(Num); i += 2)  
        if (Num % i == 0){  
            printf("NO");  
            return 0;  
        }  

标签:c语言, 计蒜客, 挑战难题

已有 5 条评论

  1. 鲸头鹳 鲸头鹳

    没有优化的那一段代码怎么在条件不符合的时候输出yes啊。。。试了半天

  2. 鞋不穿 鞋不穿

    说的好清楚,知道自己的代码不足之处在哪里了。

  3. 乐

    讲得好清楚啊...

  4. 黑啊黑啊黑啊 黑啊黑啊黑啊

    学个编程容易吗

  5. 的

    真tm难

添加新评论