UDP广播协议叫吃饭


私信TA

用户名:Mustenaka

访问量:133994

签 名:

个人博客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>
int isprime(int m)
{
    int i = 2;
    for (i = 2; i <= m / 2; i++)
    {
        if (m % i == 0) break;
    }
    if (i>m/2) return m;
    else return 0;
}
int main()
{
    int m, n, sum = 0;
    scanf("%d%d", &m, &n);
    for (; m <= n; m++)
    {
        sum = sum + isprime(m);
    }
    printf("%d", sum);
    return 0;
}为什么我这样写是错的啊?求解求解
2023-09-28 16:20:46
#include<stdio.h>
int isprime(int x);
int main()
{
	int m,n;
	scanf("%d%d",&m,&n);
	if(m<=1)  //如果m小于等于1,由于1不是素数,则赋值m为2
	m=2;
	int x,sum=0;
	for(x=m;x<=n;x++)
	{
	    if(isprime(x)==1)
	    {
	        sum+=x;
	    }
	}
	printf("%d",sum);
	return 0;
}
int isprime(int x)
{
    if(x==2)
        return 1;
    for(int i=2;i<x;i++)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
2023-05-22 23:15:19
大佬们,为啥子函数isprime()返回值不能用bool???
2023-01-29 20:44:27
各位大神,给孩子看看吧,找不到哪里出错了,感谢。
#include<stdio.h>
#include<math.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\n", sum);
	return 0;
}

bool isprime(int x)
{
	for(int i = 2; i <= sqrt(x); i++)
	   {
	   	if(x % i == 0)
	   	    return false; 
	   	printf("AAAA\n");
	   }
	return true;
}
2023-01-29 19:25:49
#include<stdio.h>

int isprime(int x);

int main()
{
	int m, n, i;
	int sum = 0;
	scanf("%d %d", &m, &n);
	for (i = m; i <= n; i++) {
		isprime(i);
		if (!isprime(i)) {
			sum += i;
		}
	}

	printf("%d\n", sum);
	return 0;
}

int isprime(int x)
{
	int j;
	int q = 0;
	for (j = 2; j <= x / 2; j++) {
		if ((x % j) == 0) {
			q = 1;
			break;
		}
	}
	return q;
}

为啥结果不对呢?
2022-10-16 17:18:26
#include<stdio.h>
int main()
{
	int m,n;
	scanf("%d%d",&m,&n);
	int x,sum=0;
	for(x=m;x<=n;x++)
	{
	    if(isprime(x)==1)
	    {
	        sum+=x;
	    }
	}
	printf("%d",sum);
	return 0;
}
int isprime(int x)
{
    if(x==2)
        return 1;
    for(int i=2;i<x;i++)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
确实是不知道哪里错了,那个大佬,帮帮忙,指点迷津呀!
2022-03-20 20:46:02
for(int i=5; i<=sqrt(num); i+=6) {
        if(num%i==0||num%(i+2)==0) {
            return false;
        }
    }
这个应该怎么理解呀?不懂......
2022-03-08 10:29:24
#include <stdio.h>

int isprime();

int main()
{
	int m=0,n=0;
	int sum=0;
	int i=0;
	
	scanf("%d %d",&m,&n);
	
	for(i=m;i<=n;i++){
		isprime(i);
		if(isprime(i)==1){
			sum+=i;
		}
	}
	
	printf("%d",sum);
	
	return 0;
} 
int isprime(int a)
{
	int i;
	int c=1;
	for(i=2;i<a;i++){
		int b=a%i;
		if(b==0){
			int c=0;
		}
	}
	return c;
}
老哥们,编译不通过,能帮忙捉虫吗:(
2022-01-10 16:57:23