C语言学习笔记20260519—如何判断输入的自然数是否为素数
如何判断输入的自然数是否为素数
1. 素数知识点
1）素数是大于 1，除了 1 和它自己，别的数都除不尽它的自然数 。
2）素数：只能被 1 和自己整除（因子数 = 2）
3）非素数：因子数 > 2 或 = 1
2.算法知识点
1）从i=1开始循环，判断输入的数num%i为0就是num的因子，而且因子是成对出现的。
2）循环条件是i小于等于num的平方根，比如16的成对因子为（1&4）、（2&8）,（4&4）循环条件只用i=4就行；输入的是平方数，在计算因子数量时，需要因子对2-1，因为有一对因子是同样的数。
3）sqrt(num),如果要用sqrt必须要包含#include <math.h>，否则计算sqrt (3) 不会等于 1.732，编译器会把它当成 0 或者随机数。这样程序就会跑乱。可以用ii <= num条件来代替。
4）程序分步设计思路：先循环过程中打印所有因子，并把因子存放在数组arr[]中（存放数组时一次存放一对因子，所以数字位号K循环一次需要+2），然后再打印数组跟循环过程中打印的因子对比，输出结果一样之后再用冒泡法从小到大排列数组并打印出来。
#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>//#include <math.h>intmain(){intnum=0;inti=0;intj=0;intk=0;inttemp=0;intcount=0;// 统计因子个数printf("请输入一个大于1的自然数：\n");scanf("%d",&num);intarr[1000];printf("\n");//素数是大于 1，除了 1 和它自己，别的数都除不尽它的自然数 。// 素数：只能被 1 和自己整除（因子数 = 2）//非素数：因子数 > 2 或 = 1// 1因字数只有1个，不是素数，输入合法性判断if(num<=1){printf("%d不是素数\n",num);return0;}printf("%d的因子数为：\n\n",num);// 只需循环到 sqrt(num),如果要用sqrt必须要包含#include <math.h>，否则sqrt (3) 不会等于 1.732，编译器会把它当成 0 或者随机数for(i=1;i*i<=num;i++)//等同 for (i = 1; sqrt(num); i++){if(num%i==0){count++;// 避免平方数重复计数，比如输入4，因子为（1&4）（2&2）2相同只能算一个，count不能在执行++//因子会成对出现，只不过平方出现是2个同样的数，因子数只能算一个if(i!=num/i){count++;j=num/i;printf("%d %d ",i,j);arr[k]=i;arr[k+1]=j;k=k+2;}else{printf("%d ",i);arr[k]=i;}}}printf("\n\n");printf("因子数组输出结果为：\n\n");//打印所有因子for(i=0;i<count;i++){printf("%d ",arr[i]);}printf("\n\n");//因子冒泡法从小到大排序for(i=0;i<count-1;i++){for(j=0;j<count-1-i;j++){// 前一个比后一个大，交换if(arr[j]>arr[j+1]){temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}//按从小到大循序打印所有因子printf("因子从小到大输出结果为：\n\n");for(i=0;i<count;i++){printf("%d ",arr[i]);}printf("\n\n");// 正确判断：素数的因子数量 == 2if(count==2){printf("%d的因字数只有%d个.\n\n",num,count);printf("%d 是素数\n",num);}else{printf("%d的因字数大于2个，总共有%d个.\n\n",num,count);printf("%d不是素数\n",num);}return0;}