2003年秋浙江省计算机等级考试二级C 编程题(2) （C/C++代码）优化判断哟

这是质数的定义：

        质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数

那么对于从1~10这个阶段的数字而言，质数的判断可以是这样的：

1:1*1                //1不包括哟

2:1*2                //是质数

3:1*3                //是质数

4:1*4 || 2*2      //不是质数

5:1*5                //是质数

6:1*6 || 2*3     //不是质数

7:1*7                //是质数

8:1*8 || 2*4        //不是质数

9:1*9 || 3*3        //不是质数

10:1*10 || 2*5    //不是质数

从这么一个规律来看，10以内的质数有2，3，5，7四个，其判断规律可以由程序归纳为，从1到其自身，存在任意两个数字想成等于其自身的数字就不是质数，写成代码可以写成这样：

bool isprime_lowbee(int n){
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(i*j==n)
                return true;
    return false;
}

这样基本的思路就完成了，可是这里会发现一个问题，就是运算太多，太重复了，其时间复杂度粗略可以相当于O(N^2)///////如果你还不明白什么是时间复杂度，你可以先理解为这个程序进行计算所需要的时间开销太高了，在以后学习中，你会明白什么是时间复杂度的。//////////

    由于大量的重复计算，我们统计一下规律，可以发现代码可以修改成这样：

bool isprime_1(int num) {
	if(num<=3) {
		return num>1;
	}
	for(int i=2; i<num; i++) {
		if(num%i==0) {
			return false;
		}
	}
	return true;
}

    这里特殊处理了一下小于等于3的数，因为小于等于3的自然数只有2和3是质数。

    然后，我们只需要从2开始，一直到小于其自身，依次判断能否被n整除即可，能够整除则不是质数，否则是质数。

    接着，我们拿一个数字10进行一个带入计算，当num=15时；

for中经历的计算为： i=2 判断 15%2!=0 继续计算 i=3时 15%3==0判断不是素数，其实，我们会发现这样的一个计算其实达不到 num 的平方根级别，也就是说，一般来说，在数据很低的时候，一般进行很少的次数就可以判断是否是素数了，但注意，一旦数据量多了，这个判断削减就很有必要。

    于是这个代码可以对for循环进行优化，变成这个样子：

bool isprime_2(int num) {
	if(num<=3) {
		return num>1;
	}
	for(int i=2; i<=sqrt(num); i++) {
		if(num%i==0) {
			return false;
		}
	}
	return true;
}

其实优化不是很多的样子。

//////////////

接下来

    我们继续分析，其实质数还有一个特点，就是它总是等于 6x-1 或者 6x+1，其中 x 是大于等于1的自然数。

    推导一下其实不难。首先 6x 肯定不是质数，因为它能被 6 整除；其次 6x+2 肯定也不是质数，因为它还能被2整除；依次类推，6x+3 肯定能被 3 整除；6x+4 肯定能被 2 整除。那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。所以循环的步长可以设为 6，然后每次只判断 6 两侧的数即可。

代码写下来是这个样子的：

bool isprime_3(int num) {
	if(num<=3) {
		return num>1;
	}
	if(num%6!=1&&num%6!=5) {
		return false;
	}
	for(int i=5; i<=sqrt(num); i+=6) {
		if(num%i==0||num%(i+2)==0) {
			return false;
		}
	}
	return true;
}

数据量小的时候看不出来（比如说这一道题，数据量非常小，根本看不出来），但一旦数据量变大了，比如说是几千，甚至几万的数判断是否是素数，则会非常提现这样代码优化的效果。

本题完整的代码是这个样子的：

#include<bits/stdc++.h>
using namespace std;

bool isprime(int num) {
	if(num<=3) {
		return num>1;
	}
	if(num%6!=1&&num%6!=5) {
		return false;
	}
	for(int i=5; i<=sqrt(num); i+=6) {
		if(num%i==0||num%(i+2)==0) {
			return false;
		}
	}
	return true;
}

int main() {
	int n,m;
	long long ans=0;    //怕数据量太大写成long long，本题可以直接使用int
	cin>>m>>n;    //C++写法，C语言写法为： scanf("%d%d",&m,&n);
	for(int i=m; i<=n; i++) {
		if(isprime(i)) {
			ans+=i;
		}
	}
	cout<<ans<<endl;    //C++写法,C语言写法为：printf("%ld",ans);
	return 0;
}

如果对C++不太熟悉的话可以看注释修改，另外

#include<bit/stdc++.h>这个头文件为万能头文件，意思使包含了所有需要用到的头文件。

C语言可以拿

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

进行替换。

C++可以拿

#include<iostream>
#include<cmath>

进行替换