C语言判断素数，判断质素算法

刺骨的言语ヽ痛彻心扉 2022-12-26 08:27 190阅读 0赞

#### 1、判断一个数是否为质数 ####

思路：质数是指在**大于1的自然数中，除了1和它本身以外不再有其他因数的自然数**。所以从2开始进行求余，在小于自然数本身数字里没有一个数字进行求余数为0的，则证明输入的自然数是质数，否则非质数

#include <stdio.h>
    int main(){ 
        int a,b,i;
        b=0;//标记
        while (1){ 
            printf("请输入一个大于1的正整数：");
            scanf("%d",&a);
            if(a>1) break;
    
        }
        for(i=2;i<a;i++){ //质数是只能被自己整除，i<a的时候
            if(a%i==0){ //当出现i能被a整除，则说明不是质数
                b++;//b自增
            }
        }
        if(b==0){ //判断b是否有变化
            printf("%d是质数\n",a);
        }else { 
            printf("%d不是质数\n",a);
        }
        return 0;
    }

结果  
![在这里插入图片描述][202012040018581.png]  
![在这里插入图片描述][2020120400193718.png]

#### 2、找出一个大于1的自然数中所有的质数并输出，计算总共多少个 ####

思路：从该自然数开始进行判断是否为质数，如果是质数则打印，接着自然数在大于1时循环做自减，再依次判断是否为质数，如果是质数则打印，在通过一个变量的自增记录为质数的个数

#include <stdio.h>
    int main(){ 
        int a,b,c,i;
        b=0;
        scanf("%d",&a);
        for(a;a>1;a--){ 
            c=0;
            for(i=2;i<=a;i++){ 
                if(a%i==0){ 
                    c++;
                    if(a==i&&c==1){ 
                        printf("%d ",a);
                        b++;
                    }
                }
            }
        }
        printf("\n总共质数为：%d",b);
        return 0;
    }

结果  
S1区间1——72，有素数18个，孪生素数7对。（2和3不计算在内，最后的数是孪中的也算在前面区间。）  
![在这里插入图片描述][20201204003109616.png]

#### 3、计算大于2的正整数有哪些素数组成，如45=3 \*3 \*5 ####

思路：素数一般指质数。质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。 因此就是把数字拆分成一个个质数数进行相乘，因此需从2开始进行求余数为0情况，如果余数为0，则自然数（a）更新为自然数（a）/2的值，进行进行下一轮求余数为0，余数不为0，在进行2的自增，继续求余为0，直到2变成一个大于自然数（a）的数值在停止求余为0的判断。

#include <stdio.h>
    int main(){ 
        int a,b;
        printf("请输入大于2的正整数:");
        while(1){ 
            scanf("%d",&a);//a是键盘输入的数字
            if(a>2) break;
            else printf("请输入大于2的正整数:");
        }
        b=2;//b初始为2
        printf("%d=",a);//打印a=
        while(b<=a){ //b不能大于a，每次循环a的数据或者b的数据会进行更新
            if(a%b==0){ //当b能被a整除且b不等于0
                printf("%d*",b);//打印
                a=a/b;//a更新 a=a/b
            }else if(a%b==0&&a==b){ //b能被a整除，且a=b
                printf("%d",b);
                a=a/b;//a更新后，a=1，循环结束
            }else{ 
                b++;//无法整除，b自增
            }
        }
        return 0;
    }

结果

![在这里插入图片描述][20201204005113157.png]![在这里插入图片描述][20201204005141194.png]

[202012040018581.png]: /images/20221120/8cf7a2df183d45f88f53cfec75177651.png
[2020120400193718.png]: /images/20221120/a42ebbbabc994773b393481555e21ad0.png
[20201204003109616.png]: /images/20221120/cc02e800396b4a31977416b918810f3d.png
[20201204005113157.png]: https://img-blog.csdnimg.cn/20201204005113157.png
[20201204005141194.png]: https://img-blog.csdnimg.cn/20201204005141194.png