C语言判断素数的3种方法(附带源码)
素数在数学中具有特殊的地位,它们是只有两个正因数(1和自身)的自然数。素数在密码学、计算机科学和数论中有着广泛的应用。
首先要先明白素数的定义:除了 1 和本身之外,没有其他的因数的数,即不能被其他数整除。
C语言代码如下:
C语言代码如下:
这种方法的优势在于,它减少了不必要的循环迭代,因为如果 n 不是素数,它必定有一个因数小于或等于其平方根。
声明:《C语言系列教程》为本站“54笨鸟”官方原创,由国家机构和地方版权局所签发的权威证书所保护。
首先要先明白素数的定义:除了 1 和本身之外,没有其他的因数的数,即不能被其他数整除。
同时要注意,1不是素数。
以下是用C语言判断素数的 3 种方法,并附带了源码和注释。1. 循环判断法
在这种方法中,我们从 2 开始,一直到输入的数字 i,逐步检查是否有任何数字能整除 i:- 如果发现这样的数字,循环将提前终止,表明 i 并非素数;
- 如果循环完整执行,未发现任何因数,那么 i 便是一个素数。
C语言代码如下:
#include<stdio.h> int main() { int i, m; printf("请输入一个大于1的整数:"); scanf("%d", &i); for (m = 2; m <= i; m++){ if (i % m == 0){ //当2-m之间遇到因数时,结束循环 break; } } if (m == i){ //如果遇到的因数就是它本身,是素数 printf("%d是素数", i); }else{ printf("%d不是素数", i); } return 0; }
2. 因数计数法
此方法通过统计一个数字的因数数量来判断其是否为素数。初始化一个计数器 count,然后从 1 遍历到输入的数字 i,每找到一个因数,计数器就增加。如果最终计数器的值为 2,那么 i 就是一个素数。C语言代码如下:
#include<stdio.h> int main() { int i, m; int count = 0; printf("请输入一个大于1的整数:\n"); scanf("%d", &i); for (m = 1; m <= i; m++){ if (i % m == 0){ //统计要判断的数的因数个数 count++; } } if (count == 2){ //如果只有2个因数 printf("%d是素数", i); }else{ printf("%d不是素数", i); } return 0; }
3. 平方根优化法
利用数学中的平方根概念,这种方法通过计算输入数字 n 的平方根 m,并只检查从 2 到 m 的整数是否能整除 n。这种方法的优势在于,它减少了不必要的循环迭代,因为如果 n 不是素数,它必定有一个因数小于或等于其平方根。
此代码中引用了求平方根 sqrt() 函数,所以要引用 math.h。
C语言代码如下:#include<stdio.h> #include<math.h> //求平方根需要引用 int main() { int n, m, i; //定义需要用到的变量 printf("请输入一个大于1的正整数:"); scanf("%d", &n); //输入要判断的数 m = sqrt(n); //求输入数的平方根 for (i = 2; i <= m; i++){ //取2-m之间的每一个整数 if (n % i == 0){ //判断能否整除n break; //非素数,跳出循环 } } if (i > m){ printf("%d是素数!\n", n); //循环正常结束,是素数 }else{ printf("%d不是素数!\n", n); //循环中途退出,不是素数 } return 0; }
补充说明
素数的分布是不规则的,但通常在自然数中,随着数值的增大,素数的密度逐渐减小。声明:《C语言系列教程》为本站“54笨鸟”官方原创,由国家机构和地方版权局所签发的权威证书所保护。