C语言中判断素数(求素数)的思路与方法实例

花思嘉

前言

素数又称质数。所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。
思路1)：因此判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。
思路2)：判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~  之间的每一个整数去除就可以了。如果 m 不能被 2 ~  间任一整数整除，m 必定是素数。例如判别 17 是是否为素数，只需使 17 被 2~4 之间的每一个整数去除，由于都不能整除，可以判定 17 是素数。
原因：因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于 ，另一个大于或等于 。例如 16 能被 2、4、8 整除，16=2*8，2 小于 4，8 大于 4，16=4*4，4=√16，因此只需判定在 2~4 之间有无因子即可。

思路1实现：

1. #include <stdio.h>
   
2. int main() {
   
3.     int n;
   
4.     printf("请输入一个1-100之间的整数：\n");
   
5.     scanf("%d", &n);
   
6. 
   
7.     int m = 0;
   
8.     for (int i = 2; i < n; i++ ) {
   
9.         if(n % i  == 0) {
   
10.             m++;
    
11.         }
    
12.     }
    
13.     if (m == 0) {
    
14.         printf("%d是素数\n", n);
    
15.     } else {
    
16.         printf("%d不是素数\n", n);
    
17.     }
    
18.     return 0;
    
19. }

复制代码

思路2实现：

1. #include <stdio.h>
   
2. #include <math.h>
   
3. int main() {
   
4.     int n;
   
5.     printf("请输入一个1-100之间的整数：\n");
   
6.     scanf("%d", &n);
   
7. 
   
8.     int i = 0;
   
9.     int q = sqrt(n);
   
10.     for (i = 2; i <= q; i++ ) {
    
11.         if(n % i  == 0) {
    
12.             break;
    
13.         }
    
14.     }
    
15.     if (i > q) {
    
16.         printf("%d是素数\n", n);
    
17.     } else {
    
18.         printf("%d不是素数\n", n);
    
19.     }
    
20. 
    
21.     return 0;
    
22. }

复制代码

《C与指针》4.14 - 2:

打印1~100之间所有质数：

1. #include <stdio.h>
   
2. int main() {
   
3.     int num, divisor;
   
4.     printf("1, 2");
   
5.     for (num = 3; num <= 100; num += 2) {
   
6.         for(divisor = 3; divisor < num; divisor +=2 ) {
   
7.             if (num % divisor == 0) {
   
8.                 break;
   
9.             }
   
10.         }
    
11. 
    
12.         if(divisor >= num) {
    
13.             printf(", %d", num);
    
14.         }
    
15.     }
    
16.     printf("\n");
    
17.     return 0;
    
18. }

复制代码

结果：

1. 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

复制代码

补充：判断素数的4种方法实例

[code]#include#include//方法一：从1-n挨个判断； bool isPrimel_1(int n) {        for(int i=2;i

大明湖的莲藕姨

感谢分享~~~~感谢分享~~~~

牡老虎呱呱衔

感谢分享~~~~感谢分享~~~~

担船群烈情

感谢楼主分享。

desww

感谢楼主，顶。