UDP广播协议叫吃饭


私信TA

用户名:Mustenaka

访问量:133992

签 名:

个人博客www.mustenaka.cn

等  级
排  名 12
经  验 23607
参赛次数 8
文章发表 196
年  龄 3
在职情况 学生
学  校 Sky_box
专  业 NE

  自我简介:

欢迎光临我的博客www.mustenaka.cn,Python,C#,U3D,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>

进行替换

 

0.0分

28 人评分

  评论区

#include<stdio.h>
#include<string.h>
#include<math.h>
int isprime(int x){
    int j;
    if(x==1)
    {
        return 0;
    }
    if(x==2)
    {
        return 1;
    }
    if(x>2)
    {
        for(j=2;j<x;j++)
        {
            if(x%j==0)
            {
                return 0;
            }
            else
                {return 1;}
        }
    }


}

int main(){
      int sum=0,i,j,m,n;
      scanf("%d%d",&m,&n);
      for(i=m;i<=n;i++)
      {
          if(isprime(i)==1)
          {
              sum+=i;
          }
      }
      printf("%d",sum);
}
这怎么错了啊  大神们
2021-11-25 10:12:26
I need help !!!where is my problem,I can't find it!!!
#include<stdio.h>
#include<stdbool.h>
bool isprime(int x);
int main()
{
	int m,n,sum=0;
	scanf("%d%d",&m,&n);
	for(int i=m;i<=n;i++)
	{
	    if(isprime(i))
	        sum+=i;
	}
	printf("%d",sum);
	return 0;
}
bool isprime(int x)
{
    if(x==2)return true;
    for(int j=2;j<x;j++)
    {
        if(x%j==0)return false;
    }
    return true;
}
2021-11-21 15:48:09
为什么不优化,输出答案就不对了
2021-05-11 22:40:41
大神给我看看哪里错了,谢谢
#include<stdio.h>
#include<math.h>
int isprime(int x)
{
	if(x==1||x==2||x==3||x==5) return 1;
	for(int i=2;i<=sqrt(x);i++)
	{
	  else if(x%i==0) return 0; }
}
int main()
{
	int n;
	int sum=0,i;
	while((scanf("%d",&n)!='\n'&&isprime(n)))
	{
		sum+=n;
		printf("%d",sum);
	}
	return 0;
}
2021-03-14 12:06:09
#include"stdio.h"
#include"math.h"
int isprime(const int n)
{
int i;
for (i=2;i<=(int)floor(sqrt(n));++i)
if (n%i==0) return 0;
return 1;
}
main()
{int m,n,i,s,j=0;
scanf("%d%d",&m,&n);
int a[n-m+1];
 for(i=0;i<n-m+1;i++)
 a[i]=i+m;
 for(i=0;i<n-m+1;i++)
 {s=isprime(a[i]);
 if(s==1)j=j+a[i];}
 printf("%d",j);	
}
有没有大神给看看错哪了
2020-12-30 20:17:55
赞,又学了一招
2019-10-25 14:10:20
#include<stdio.h>
int sum=2;
void isprime(int x){
	for(int i=2;i<x;i++){
		if(x%i==0){
			break;
		}else if(i==x-1){
			sum+=x;
		}
	}
}
void main(){
	int m,n,x;
	scanf("%d%d",&m,&n);
	for(x=m;x<=n;x++){
		isprime(x);
	}
	printf("%d\n",sum);
}
2019-02-20 20:28:56
超级良心!!
2019-01-19 23:17:06