UDP广播协议叫吃饭


私信TA

用户名:Mustenaka

访问量:1453

签 名:

大家别被考试得0分给骗了,他其实是贺州学院最强的人!

排  名 49
经  验 4286
参赛次数 3
文章发表 73
年  龄 3
在职情况
学  校 Sky_box
专  业 NE

  自我简介:

この青春の始まりを、悔しいのないように大切にしたい。

这是质数的定义:

        质数又称素数。一个大于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>

进行替换

  评论区