每日一题：素数求解

先看素数(质数)定义：

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

更加详细的信息请看链接：质数_百度百科 (baidu.com)

今天的几道题目基本都是围绕素数展开的，求解素数的基础就是先能找出1~100之间的素数，这个是最最简单的题目，而这道题目曾经却是有些企业的面试官经常问的，让你不断得去优化代码，考察你的能力，有过面试官写过一篇文章，推荐大家可以去仔细看一下： 素数求解的n种境界

我们来看今天的比较简单的题目：

输出1~n之间所有的素数

//输出1~n之间所有的素数
#include
#includeint main()
{int n = 0;scanf("%d", &n);int i = 0;for (int num = 1; num <= n; num+=2)//因为质数不可能为偶数，所以直接+=2即可{int count = 0;//例如前面判断过5，但是遍历的话后面还需要判断25//所以只要判断该数到它的开平方能否被整除即可，不用完全遍历，可以大大提高代码效率for (count = 2; count <= sqrt(num); count++){if (num % count == 0){break;}}if (sqrt(num) < count){printf("%d ", num);i++;}}printf("\n共有:%d个\n", i);return 0;
}

在此基础上也有许多衍生出的题目，例如：

输出1~n之间个位是1的素数，题目链接：素数__牛客网 (nowcoder.com)

//输出1~n之间个位是1的素数
#include
#include
int main()
{int n = 0;int num = 1;int i = 0;scanf("%d", &n);while (num <= n){int count = 2;for (count = 2; count <= sqrt(num); count++){if (num % count == 0){break;}}if (count > sqrt(num) && num%10==1){i++;printf("%d ", num);}num+=2;}printf("\n数目:%d个\n", i);return 0;
}

求区间[M,N]内的所有素数的个数：求素数_笔试题牛客网 (nowcoder.com)

//求区间[M,N]内的所有素数的个数
#include
#includeint main()
{int n = 0;int m = 0;scanf("%d %d", &m,&n);int i = 0;for (int num = m; num <= n; num++){int count = 0;for (count = 2; count <= sqrt(num); count++){if (num % count == 0){break;}}if (sqrt(num) < count){i++;}}printf("%d\n", i);return 0;
}

判断是否是素数:判断是否是素数_笔试题牛客网 (nowcoder.com)

//判断是否是素数
#include
#includeint main()
{int n = 0;scanf("%d",&n);int i = 0;for (i = 2; i <= sqrt(n); i++){if (n % i == 0){break;}}if (i > sqrt(n)){printf("true\n");}else{printf("false\n");}return 0;
}