这是质数的定义:
质数又称素数。一个大于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 <iostream> #include <cstring> using namespace std; class prime {public: prime() {min = 0;max = 0;} int isprime(int x); void get_value(); void sum(); private: int min; int max; }; int prime::isprime(int x){for (int i = 3; i <= x; i++){bool isprime = true;for (int j = 2; j < i; j++){if (i % j == 0){isprime = false;}}if (isprime)return x;else return 0;}} void prime::get_value(){cin >> min;cin >> max;} void prime::sum(){int sum = 0;for (int i = min; i <= max; i++){sum += isprime(i);}cout << sum << endl;} int main(){prime p1;p1.get_value();p1.sum();return 0;}求大佬帮忙看看,哪出问题了,2-5为什么是14啊
#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; }为什么我这样写是错的啊?求解求解
#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; }
大佬们,为啥子函数isprime()返回值不能用bool???
l 2023-02-24 21:57:31 |
因为c里面没有bool类型,用c++可以,你也可以返回int类型(1或0)
各位大神,给孩子看看吧,找不到哪里出错了,感谢。 #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; }
l 2023-02-24 22:03:20 |
你打印printf("AAAA ")这句是做什么呢?你可以再写一个判断是1的时候返回false,在c里面没有bool类型,可以返回数字类型或者用c++
#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; } 为啥结果不对呢?
#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-08-13 12:48:23 |
1不是素数
for(int i=5; i<=sqrt(num); i+=6) { if(num%i==0||num%(i+2)==0) { return false; } } 这个应该怎么理解呀?不懂......
C语言程序设计教程(第三版)课后习题5.6 (C语言代码)浏览:563 |
WU-格式化数据输出 (C语言代码)浏览:1818 |
1009题解浏览:802 |
大家好,我是验题君浏览:604 |
1050题解(结构体数组与结构体指针的使用)浏览:1216 |
用筛法求之N内的素数。 (C语言代码)浏览:595 |
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)浏览:487 |
C语言程序设计教程(第三版)课后习题9.1 (C语言代码)浏览:653 |
C语言训练-斐波纳契数列 (C语言代码)浏览:644 |
三进制小数 (C语言代码)浏览:903 |