方法一 :数因子个数，输入的一个数字为i,用i%n,n为2～i-1的数。如果因子count的数量为0，那么这个数则为素数。比如13除以2到12中间的每一个数字，都没有一个因子，所以13是素数。
#include<stdio.h>
int main()
{
int i, n, count=0;
// i为要判断的数字
// n为2到n-1的数字
// count为i的因子
printf("请输入一个大于等于2的数字 :"); //提示输入一个数字
scanf("%d", &i); //读取一个这个数字
for (n = 2;n < i;n++) //要有2到n-1中的每一个数字
{
if (i % n == 0)
count++; //除1和他本身之外的因子个数
}
if (count == 0)
printf("是素数");
else
printf("不是素数");
return 0;
}
方法2：
方法二: 除以2到i的数，我们看第一个能被整除的数字是多少，如果是i本身，那么是素数。否则就不是，比如13这个数字，除以2到13中的数字，只有13可以被整除，那么13就是素数，又比如9，当遍历到3时，就可以整除，而3不等于9，所以9不是素数。
#include<stdio.h>
int main()
{
int i=0, n;
printf("请输入一个数字:");
scanf("%d", &i); //从键盘获取一个数字
for (n = 2;n <= i;n++) //遍历从2到i的数字
{
if (i % n == 0) //如果遍历到有一个数n，能被n整除，则循环结束
break;
}
if (n == i) //如果那个因子就是它本身，那么i就是素数，否则不是
printf("是素数");
else
printf("不是素数");\
return 0;
}
腾讯曾考过一个面试题目：请你判断1456789876541是不是素数 （结论：是）
这个1456789876541数字已经到达了万亿级别，很大很大，如果按照之前的想法来一个一个循环，那么程序会很慢。所以怎么办呢？
接下来，我们来一起看看这个代码是如何进行优化的，在这之前,我们先来看一个证明：
若一个数n不是素数，则n可以写成n=a*b的形式（假设a<=b,且a不等于1），且n=(n^1/2)*(n^1/2)
则我们不难推出：a<=n^1/2 ,a是n的一个因子，也就是说，我们并不需要取完2到i-1或i中间的每一个数字，我们只需要看一看2到n^1/2之间有没有可以整除的。如果没有就为素数，如果有就不是素数。一开始我和大家一样，不明白为什么要这么做，后来我明白了。当问题的规模很大很大时，我们要遍历2到n中间的每一个数字，那么程序就会很慢，而工作中，时间是很宝贵的，所以代码的优化很重要。
我们只需要把上面的代码中的for循环改为for(n=2;n<=sqrt(i);n++) 其他内容不变，解释一下sqrt()是开根号的意思，需要引用一下头文件##include<math.h>。看一下
方法一的优化：
//方法一的优化
#include<stdio.h>
#include<math.h>
int main()
{
long long i, n, count=0;//当我们要判断1456789876541这个数字时，我们就要定义的数据类型要大
// i为要判断的数字
// n为2到n-1的数字
// count为i的因子
printf("请输入一个大于等于2的数字 :"); //提示输入一个数字
scanf("%lld", &i); //读取一个这个数字，注意lld
for (n = 2;n<sqrt(i);n++) //要有2到n-1中的每一个数字
{
if (i % n == 0)
count++; //除1和他本身之外的因子个数
}
if (count == 0)
printf("是素数");
else
printf("不是素数");
return 0;
}
方法二的优化
#include<stdio.h>
#include<math.h>
int main()
{
long long i=0, n;
printf("请输入一个数字:");
scanf("%lld", &i); //从键盘获取一个数字
for (n = 2;n <= sqrt(i);n++) //遍历从2到i的数字
{
if (i % n == 0) //如果遍历到有一个数n，能被n整除，则循环结束
break;
}
if (n == i) //如果那个因子就是它本身，那么i就是素数，否则不是
printf("是素数");
else
printf("不是素数");
}
创作不易， 如果这份博客👍对你有帮助，可以给博主一个免费的点赞以示鼓励。
欢迎各位帅哥美女点赞👍评论⭐收藏⭐，谢谢！！！
如果有什么疑问或不同的见解，欢迎在评论区留言哦👀。
祝各位生活愉快⭐
文章出处登录后可见！
