【C语言】判断一个数是否为素数

简介: 【C语言】判断一个数是否为素数

判断一个数是否为素数

素数和质数没有区别,素数又叫质数,质数是指在大于1的自然数中,除了1和它本身以外,不能被其他自然数整除的数。比1大但不是素数的数称为合数,1和0既非素数也非合数。”

所谓素数,是指除了1和其本身外,不能被其它任何整数整除的正整数,2是最小的素数。

现在,用户输入一个整数,判断它是否为素数


方法1

是指除了1和其本身外,不能被其它任何整数整除的正整数

for循环遍历2~输入的数值num,num对这些数取余(求模),余数是0代表能整除,代表不是素数,如果不是素数,标志位置1,跳出循环判断标志位的状态即可

1. #include <stdio.h>
2. 
3. int main(void) {
4.  int i, j;
5.  int num;
6.  char flag = 0;  //0代表是素数,1代表不是
7.  scanf("%d", &num);  //输入
8. 
9.  for (i = 2; i < num; i++) {
10.     if (num % i == 0) { //如果能整除,标志位置1
11.       flag = 1;
12.     }
13.   }
14. 
15.   if (flag == 1)  //判断标志位即可知是否为素数
16.     printf("%d不是素数\n", num);
17.   else
18.     printf("%d是素数\n", num);
19.   return 0;
20. }

方法2  

当一个数不是质数时,必定存在两个约数,一个大于等于sqrt(n),另一个小于sqrt(n)。利用这种特性,可以对方法1进行改进,只判断数n能否被小于sqrt(n)的数整除。

小于平方根和大于平方根的部分是一一对应的,因而可以只判断从2到平方根的数字是否都能被整除即可。

2.1

1. #include <stdio.h>
2. #include <math.h>
3. 
4. int main() {
5.  int num, k, i;
6.  char flag = 0;
7.  scanf("%d", &num);
8. 
9.  k = sqrt(num);  //先开平方,减小运算量
10.   for (i = 2; i <= k; i++) {
11.     if (num % i == 0) {
12.       flag = 1;
13.       break;  //只要有能整除的数,就跳出循环判断,减小运算量
14.     }
15.   }
16. 
17.   if (flag == 1)  //判断标志位即可知是否为素数
18.     printf("%d不是素数\n", num);
19.   else
20.     printf("%d是素数\n", num);
21.   return 0;
22. }

2.2

1. #include <stdio.h>
2. #include <math.h>
3. 
4. int main() {
5.  int m, k, i;
6.  scanf("%d", &m);
7. 
8.  k = sqrt(m);
9.  for (i = 2; i <= k; i++) {
10.     if (m % i == 0)    //只要有能整除的数,就跳出循环判断,减小运算量
11.       break;
12.   }
13. 
14.   if (m >= 2) {
15.     if (i > k)
16.       printf("%d is a prime.", m);
17.     else
18.       printf("%d is not a prime.", m);
19.   } else
20.     printf("%d is not a prime.", m);
21.   return 0;
22. }

进阶:输出区间长度内的素数

比如打印1000到2000内的素数

1. #include <stdio.h>
2. 
3. int main() {
4.  int i = 1000;
5.  while (i <= 2000) {
6.    int flag = 0;
7.    int j = 2;
8. 
9.    while (j < i) {
10.       if (i % j == 0) {
11.         flag += 1;
12.       }
13.       j = j + 1;
14.     }
15.     if (flag == 0) {
16.       printf("%d\n", i);
17.     }
18.     i = i + 1;
19.   }
20.   printf("\n");
21.   return 0;
22. }

用函数封装一下,直接调用这个函数即可输出素数

1. #include <stdio.h>
2. 
3. void prime(int x, int y) // 区间(x,y)
4. {
5.     int num; // 当前判断的数
6.     char flag = 0;
7.     // 外层循环,遍历区间(x,y)内的数
8.     for (int j = x; j <= y; j++)
9.     {
10.         num = j;
11. 
12.         // 内层循环,判断当前数,是否为素数
13.         for (int i = 2; i < num; i++)
14.         {
15.             if (num % i == 0) // 能整除,就不是素数
16.             {
17.                 flag = 1;
18.                 break; // 跳出内层循环,遍历下一个数
19.             }
20.         }
21. 
22.         if (flag == 0)
23.             printf("%d\n", num);
24. 
25.         flag = 0; // 在判断下一个数之前,先把标志位置0
26.     }
27. }
28. 
29. int main()
30. {
31.     prime(1000, 2000);
32. }


相关文章
|
C语言
C语言之完数、素数、回文数合集
C语言之完数、素数、回文数合集
181 0
|
C语言
【01】判断素数/质数(C语言)
【01】判断素数/质数(C语言)
|
C语言
C语言Oj题判断素数几种方式详解
输入一个数判断它是不是素数,并且不是的情况把它打印出来不是素数。
144 1
|
9月前
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
379 23
|
C语言
C语言初阶:如何判断是否为素数并且输出
C语言初阶:如何判断是否为素数并且输出
108 0
|
C语言
【C语言】输入一个数n,输出从n到n+100的范围内所有的素数,并统计素数的个数
【C语言】输入一个数n,输出从n到n+100的范围内所有的素数,并统计素数的个数
541 0
|
C语言
C语言----寻找100~999范围内的质数--素数
C语言----寻找100~999范围内的质数--素数
593 3
|
C语言
【C语言刷题每日一题】——打印100到200之间的素数
【C语言刷题每日一题】——打印100到200之间的素数
|
C语言 Windows
C语言素数的不同求法
C|素数的不同求法及在线测试比较
|
C语言
C语言---函数----100~n之间的素数
C语言---函数----100~n之间的素数
111 1