C语言——素数的详解

发布时间:2024年01月08日

一、什么是素数

素数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

1不是素数、2是素数。

二、判断一个数是否为素数(循环)

分析思路:输入一个数n,使n除2、n除3....n除n-1若出现整除,则不是素数。

当出现一个整除的时候,我们要停止循环。为了利于表达,我们可以引入一个标志flag=1,代表n为素数;当flag=0的时候,n不是素数。

输入:1、2、12、71

输出:1不是素数、2是素数、12不是素数、71是素数

代码如下

#include <stdio.h>
int main ()
{  int n;
   scanf("%d",&n);
   int flag=1;
   if(n==1)
   {
  	  flag=0; //如果n=1,flag=0,即不是素数。单独讨论1和2.
   }
   if(n>2)
   {
    	for(int i=3;i<n;i++)
       {
  	       if(n%i==0)
  	       {
  	 	     flag=0;
		     break; 
	       }
       } 
   }
  
  if(flag==0)
     printf("%d不是素数",n);
  else
     printf("%d是素数",n);
return 0;
}

输出情况:

?三、函数计算给定区间内素数和的函数

? ??函数接口定义:

? ? ? ? ? ? ? ? ? ? ? ? ? ?int prime( int p );
? ? ? ? ? ? ? ? ? ? ? ? ? ?int PrimeSum( int m, int n );

其中函数prime当用户传入参数p为素数时返回1,否则返回0;

函数PrimeSum返回区间[m,?n]内所有素数的和。题目保证用户传入的参数mn

输入:-1 10
输出:Sum of ( 2 3 5 7 ) = 17

本题分析:

1、是区间内判断函数,所以需要一个for循环取区间内的数进行判断

2、本题需要书写两个函数,一个是判断素数函数,一个是素数求和函数。涉及函数的声明、调用、书写。

代码如下:

#include <stdio.h>
#include <math.h>

int prime( int p );
int PrimeSum( int m, int n );
    
int main()
{
    int m, n, p;

    scanf("%d %d", &m, &n);             //输入区间
    printf("Sum of ( ");                //输出:Sum of(
    for( p=m; p<=n; p++ )               //用for循环判断区间内的所有函数
	 {             
        if( prime(p) != 0 )             //调用函数
            printf("%d ", p);           //输出素数
     }
    printf(") = %d\n", PrimeSum(m, n));  //输出:)=sum

    return 0;
}

int prime( int p )    //判断素数
{
    int i,flag=1; 
    if(p<=1) 
        return 0;
    if(p==2) 
        return 1;
    for(i=2;i<p;i++)
	{ 
        if(p%i==0)
		{
            flag=0;
            break;
        }
    }
    return flag;
}

int PrimeSum( int m, int n )  //求和
{
	int i,sum=0;
	for(i=m;i<=n;i++)
	{
		if(prime(i))    //调用prime()函数
		sum+=i;
	}
	return sum;
}

?输出情况

四、循环判断素数的优化

改编(二)用函数判断区间内所有的素数。

我们有代码

#include <stdio.h>
#include <math.h>

int prime( int p );
int PrimeSum( int m, int n );
    
int main()
{
    int m, n, p;

    scanf("%d %d", &m, &n);             //输入区间
    for( p=m; p<=n; p++ )               //用for循环判断区间内的所有函数
	 {             
        if( prime(p) != 0 )             //调用函数
            printf("%d ", p);           //输出素数
     }

    return 0;
}

int prime( int p )    //判断素数
{
    int i,flag=1; 
    if(p<=1) 
        return 0;
    if(p==2) 
        return 1;
    for(i=2;i<p;i++)
	{ 
        if(p%i==0)
		{
            flag=0;
            break;
        }
    }
    return flag;
}

输入 -1 10

?

?得出的结果是正确的,但是假设我们验证的是7那么循环要走5次,无疑是非常浪费时间的因此我们可以优化一下代码。

(1)除了2以外只要是偶数一定不是素数,所以我们可以在函数循环中去掉偶数,让i=3开始每次+2

函数代码如下

int prime( int p )    //判断素数
{
    int i,flag=1; 
    if(p<=1||(p%2==0&&p!=2)) //如果p<=1或者是偶数但不是2,直接使flag=0
     {
     	flag=0;
	 }
    for(i=3;i<p;i+=2)   //i从3开始,每次判断后加2,不除偶数
	{ 
        if(p%i==0)
		{
            flag=0;
            break;
        }
    }
    return flag;
}

运行情况

这样如果判断7是不是素数只需要循环2次,那么数字越大,循环的优化也会越明显

(2)在(1)的基础上,我们不循环到x-1,而是循环到x的平方根,也就是假设我们判断100是不是素数,我们不用循环到99,而是循环到10就可以了。

函数代码如下

int prime( int p )    //判断素数
{
    int i,flag=1; 
    if(p<=1||(p%2==0&&p!=2))
     {
     	flag=0;
	 }
    for(i=3;i<=sqrt(p);i+=2)
	{ 
        if(p%i==0)
		{
            flag=0;
            break;
        }
    }
    return flag;
}

总结

素数是一个初学者的难题,算是初学者的小坑之一,需要选择、循环、函数的融会贯通。

等学到数组之后,我们可以设立一个素数表,使其判断素数的速度更快

?

文章来源:https://blog.csdn.net/m0_69916575/article/details/124600643
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。