一、素数的定义

素数又称质数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数。

1既不是素数也不是合数。

下图来自百度百科，500以内的质数表。

质数（素数）的应用：

https://baike.baidu.com/item/%E8%B4%A8%E6%95%B0/263515?fromtitle=%E7%B4%A0%E6%95%B0&fromid=115069&fr=aladdin

质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。

在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。

在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。

以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

多数生物的生命周期也是质数（单位为年），这样可以最大程度地减少碰见天敌的机会。

 

二、题目描述

输入一个正整数x，判断是否为素数，如果是，打印“是”，否则打印“不是”。

三、难易程度分析

判断一个数是否是偶数，很简单：

if( x%2==0) printf("是偶数"); else printf("不是偶数");

然而，素数可没有这样简单的判断条件。因此它是一个复杂问题。

四、从约数个数着手求解

素数 x 只有1和本身两个约数。

因此对[1,x]，统计x的约数的个数 count，如果count==2，则x就是素数。

#include <stdio.h> int isPrime(int x) {//如果x是素数，返回1，否则返回0 if(x<=1) return 0; int count=0,i; for(i=1;i<=x;i++) { if(x%i==0) count++; } if(count==2) return 1; return 0; } int main(void) { printf("%d\n",isPrime(1) ); printf("%d\n",isPrime(2) ); printf("%d\n",isPrime(3) ); printf("%d\n",isPrime(9) ); }

 分析：

（1）该程序可以正常工作；

（2）for循环次数可以优化，因为已经知道 1 和 x肯定是x的约数，因此从2 到 x-1 循环即可，在2到x-1之间，如果没有一个约数，就是素数。

五、循环次数优化

#include <stdio.h> int isPrime(int x) {//如果x是素数，返回1，否则返回0 if(x<=1) return 0; int count=0,i; for(i=2;i<x;i++) { if(x%i==0) count++; } if(count==0) return 1; return 0; } int main(void) { printf("%d\n",isPrime(1) ); printf("%d\n",isPrime(2) ); printf("%d\n",isPrime(3) ); printf("%d\n",isPrime(9) ); }

分析：for循环还可以优化，只要在 2 和 x-1 之间找到一个约数，就不是素数，后面就不必找了。

六、找到约数提前结束循环

#include <stdio.h> int isPrime(int x) {//如果x是素数，返回1，否则返回0 if(x<=1) return 0; int i; for(i=2;i<x;i++) { if(x%i==0) return 0; } return 1; } int main(void) { printf("%d\n",isPrime(1) ); printf("%d\n",isPrime(2) ); printf("%d\n",isPrime(3) ); printf("%d\n",isPrime(9) ); }

分析：

1、此时的程序，只要x是合数，找到第一个约数，就可以判定其不是素数。然而，对于真正的素数，比如11，从2到10，还需要试探9次。

2、我们这样分析一下，如果x有一个约数a，则必定有另一个约数b，使得 x=a*b；不失一般性，假设a<=b。

3、粗略的算，如果a在[1,x/2],则b在[x/2,x],因此只要在[2,x/2]找不到x的约数，就可以判定x是素数。这样，当x是19时，x/2是位于区间(9,10)，只需要比较8次即可判定19是素数。

4、精确的算，x=a*b，a<=b,则 a*a<=x<=b*b, a<=sqrt(x),因此只要在[2,sqrt(x)]找不到x的约数，就可以判定x是素数。这样，当x是19时，sqrt(x)是位于区间(4,5)，只需要比较4次即可判定19是素数。

七、数学的力量

#include <stdio.h> #include <math.h> int isPrime(int x) {//如果x是素数，返回1，否则返回0 if(x<=1) return 0; int i; for(i=2;i<=sqrt(x);i++) { if(x%i==0) return 0; } return 1; } int main(void) { printf("%d\n",isPrime(1) ); printf("%d\n",isPrime(2) ); printf("%d\n",isPrime(3) ); printf("%d\n",isPrime(9) ); }

后记：

从本例可以看出，恰当的运用数学，可以提高算法的效率。

尤其是当你读研究生做研究时，要对实际问题建立数学模型，编程求解，没有数学基本玩不转。