1057,素数的判断

题目描述

输入一个正整数n，判断n是否是素数，若n是素数，输出”Yes”,否则输出”No”。
输入
输入一个正整数n(n<=1000)
输出
如果n是素数输出”Yes”，否则输出”No”。输出占一行。
样例输入 Copy
2
样例输出 Copy
Yes
素数又称质数。所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数
注意：1既不是质数也不是合数

思路解析

对于素数的判断，我们有以下的思路：
暴力思路：把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。
……..
然而m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~之间的每一个整数去除就可以了。
如果 m 不能被 2 ~ 间任一整数整除，m 必定是素数。

（原因：因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于 ，另一个大于或等于 。
例如 16 能被 2、4、8 整除，16=28，2 小于 4，8 大于 4，16=44，4=√16，因此只需判定在 2~4 之间有无因子即可。）

代码分析

#include<stdio.h>
#include<math.h>
int main()
{
    int i, n, k;
    scanf("%d", &n);
    k = sqrt(n);//这个地方最推荐的写法是：k=(int)sqrt( (double)n );*1
    for(i = 2; i <= k; i++) 
        if(n % i == 0) 
            break;
//当余数为0，即在遍历区间存在除数整除现象break跳出“for”循环直接从Line14开始执行
// 如果没有完成循环中途跳出，且n不为1，则n不是素数
    if(i <= k || n == 1) 
        printf("No\n");
    else
        printf("Yes\n");
    return 0;
}
//判断部分也可以写成以下结构
if(i>k&&n!=1) //注意最后一次循环，会执行i++，此时 i=k+1，所以有i>k 
  printf("Yes\n");//1既不是质数也不是合数
else
  printf("No\n");

1：sqrt函数的原型是 double sqrt(double x);即，返回的参数和输入的参数都为double浮点类型
所以在源码中笔者推荐使用k=(int)sqrt( (double)n );
当然这道题即使写成k = sqrt(n);，且k被定义为int类型也没有出现错误，并且通过了Oj，但笔者并不推荐这样的写法。
2：另外就是一些坑，比如
大小写——Yes YES No NO之类的低级错误。
n前面没有寻址符号&。

算法进阶

先留个门在这：
线性筛的理解及应用
一般筛法求素数+快速线性筛法求素数
快速线性筛详解