©2020-2024 ioDraw All rights reserved,
Privacy Policy
一、什么是素数
素数是指在大于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; }
总结
素数是一个初学者的难题，算是初学者的小坑之一，需要选择、循环、函数的融会贯通。
等学到数组之后，我们可以设立一个素数表，使其判断素数的速度更快