搞定！用C语言快速判断一个数是否是素数的方法

最编程 2024-08-08 21:34:00

...

问题描述：判断一个数是不是素数

源代码：

第一版代码：

缺陷：

1、没有考虑1既不是素数也不是非素数。

2、for语句中，取值范围【2，n】太多了，没有必要。

#include<stdio.h>
int main (void)
{
    int i,n,sum=0;

    printf("**********************\n判断一个数是不是素数\n**********************\n素数概念：只能被1和本身整除\n\n");
    
    printf("请输入一个值：");
    scanf("%d",&n);
    
    for(i=2;i<n;i++){
        if(n%i==0){
        printf("\n%d能被%d整除\n",n,i);
        sum = sum+1;
        }
    }
    
    printf("\n%d能被%d个整数整除\n",n,sum);
    
    if(sum=0){
        printf("\n%d是素数",n);
    }else{
    
        printf("\n%d不是素数",n);
    }
    
    return 0;
 }

第二版代码：

修复第一版缺陷：

1、添加n=1时候的情况判断。

2、在判断素数过程中，由于n不可能被大于n/2的数字整除，所以原先i的取值区间可缩小为【2，n/2】，数学上能证明，该区间可以是【2，根号n】。

#include<stdio.h>
int main (void)
{
    int i,n,sum=0;

    printf("**********************\n判断一个数是不是素数\n**********************\n素数概念：只能被1和本身整除\n\n");
    
    printf("请输入一个值：");
    scanf("%d",&n);
    
    for(i=2;i<n/2;i++){
        if(n%i==0){
        printf("\n%d能被%d整除\n",n,i);
        sum = sum+1;
        }
    }
    
    printf("\n%d能被%d个整数整除\n",n,sum);
    
    if(sum=0&&i!=1){
        printf("\n%d是素数",n);
    }else{
    
        printf("\n%d不是素数",n);
    }
    
    return 0;
 }

第三版代码：

精简版代码：

只要判断是否是素数，其他不做输出，同时去掉sum变量。

#include<stdio.h>
int main (void)
{
    int i,n;

    printf("**********************\n判断一个数是不是素数\n**********************\n素数概念：只能被1和本身整除\n\n");
    
    printf("请输入一个值：");
    scanf("%d",&n);
    
    for(i=2;i<n/2;i++)
        if(n%i==0)  break;
    if(i>n/2&&n!=1)
        printf("\n%d是素数",n);
    else
        printf("\n%d不是素数",n);
        
    return 0;
 }