C语言——素数的详解

一、什么是素数

素数是指在大于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]内所有素数的和。题目保证用户传入的参数m≤n。

输入：-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;
}

总结

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

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

?