最小质因数 == 最大质因数,不等式秒了!

2024-03-31 01:04

本文主要是介绍最小质因数 == 最大质因数,不等式秒了!,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

起因:

  在洛谷做题遇到了这道题~

  一看咿呀,又是道数学题~

  首先我们要了解一下,什么是质数?

  我记得好像有年高考题的前几题好像考了这玩意来着,质数的概念好像在小学学过,上了初中后基本都没有用过了~

  质数就是素数,我们以前应该写过一个程序叫判断某个范围的数里面有多少个素数,其实在这里我们就已经了解过质数的概念了~

  以下是GPT回答的参考:

  质数和素数在数学上指的是同一个概念,两者都是只能被1和它本身整除的正整数,而且大于1。在数学文献中,通常使用“素数”这个词,特别是在欧洲和北美地区,而“质数”则更多地在亚洲和拉丁美洲使用。不过,这两个词指的是完全相同的概念。

  例如,2、3、5、7、11、13、17等都是质数(或素数),因为它们除了1和它们自身以外,没有其他的因数。相对的,像4、6、8、9、10等就不是质数(或素数),因为它们除了1和它们自身以外,还有其他的因数。

  OK,已经知道概念了,因为题目中称呼这种数为质数,我们为统一命名,后文中使用质数来称呼这种数,让我们来看看题~

  已知两个质数的乘积,求其中一个最大的质数,好像并不是很难,如果是用常规的思路的话,用判断质数的那个思路就可以解决掉这道题,前提是不限时~

  于是我第一次提交的代码是这样的~

  第一次提交的代码:

#include<iostream>
#include <iomanip>
#include<climits>using namespace std;int main()
{int a[10];int n, count = 0;cin >> n;int fact = n;for (int i = 2; i < n; i++) {if (fact % i == 0)a[count++] = i;}cout << a[count - 1] << endl;return 0;
}

  使用一个数组来存储所有可能被 n 整除的数,在数组中的数肯定都是 n 的因数,所以最后一个数组空间中存储的就是最大的质因数~

  理想很丰满,现实很骨感,果不其然超时了 T^T

  第一次提交的结果:

 想想有没有什么可以提高速度的方法?

 实际上,在判断某个数是否为质数时,只需要枚举到这个数开平方后的数(向下取整)就行了~

  为什么质数只需要枚举到这个数开平方后呢?

  首先,我们知道如果一个数 n 不是质数,那么它一定可以被表示为两个较小的正整数相乘,即 n = a * b

现在假设 a 和 b 都大于 sqrt(n)。那么我们有:
a * b = n
a > sqrt(n)
b > sqrt(n)

  从上面的不等式可以看出,a 和 b 都必须大于 sqrt(n)。但是,如果 a 和 b 都大于 sqrt(n),那么它们的乘积 a * b 一定大于 n~

  这就意味着,如果一个数 n 不是质数,那么它一定可以被表示为两个较小的正整数相乘,其中至少有一个数小于或等于 sqrt(n)~

  因此,我们只需要检查 2 到 sqrt(n) 之间的所有整数,就可以确定 n 是否为质数。如果找到任何一个能被 n 整除的数,那么 n 就不是质数。如果在这个范围内没有找到任何能被 n 整除的数,那么 n 就是质数~

  这种方法的时间复杂度是 O(√n),相比于逐一检查 2 到 n-1 之间的所有整数,效率要高得多。这就是为什么判断质数只需要列举到 i <= sqrt(n) 就够了的原因~

  但是这道题我们无法直接使用这种方法,题目中明确说了这个数是两个质数的乘积,所以这个数一定不是质数,如果使用我们上述说到的方法只会求到最小的质因数

  提交就是一片全红,因为我们只求得了最小的质因数,而不是最大的质因数  -_-

  使用上述方法的代码:

#include<iostream>
#include <iomanip>
#include<climits>
#include<cmath>using namespace std;int main()
{int a[10];int n, count = 0;cin >> n;int fact = n;for (int i = 2; i <= sqrt(n); i++) {if (fact % i == 0)a[count++] = i;}cout << a[count - 1] << endl;return 0;
}

 使用上述方法的结果:

 

  但是我们可以借助这种思路,先卖个关子~  ^v^

  既然不能取到sqrt(n),那我扩大一些范围总行了吧~

  第二次提交的代码:

#include<iostream>
#include <iomanip>
#include<climits>
#include<cmath>using namespace std;int main()
{int a[10];int n, count = 0;cin >> n;int fact = n;for (int i = 2; i < sqrt(n)*2+1; i++) {if (fact % i == 0)a[count++] = i;}cout << a[count - 1] << endl;return 0;
}

   第二次提交的结果:

  先开方,然后再对平方后的数进行扩大,这样做会有错误,因为会有一些边界条件未考虑到,比如如果数是6(2 * 3)的话,枚举到2就没了,结果肯定是错误的~

  那对sqrt(n)取整试试?

  第二次改进后的代码:

#include<iostream>
#include <iomanip>
#include<climits>
#include<cmath>using namespace std;int main()
{int a[10];int n, count = 0;cin >> n;int fact = n;for (int i = 2; i <= sqrt(n)*2+1; i++) {if (fact % i == 0)a[count++] = i;}cout << a[count - 1] << endl;return 0;
}

  第二次改进后的结果:

  可以看到还是有问题,我们的取值范围是不对的,取值范围太小了~

  那我们把取值范围扩大一点试试呢?

  第三次提交的代码:

#include<iostream>
#include <iomanip>
#include<climits>
#include<cmath>using namespace std;int main()
{int a[10];int n, count = 0;cin >> n;int fact = n;int res = 1;for (int i = 2; i < n/2; i++) {if (fact % i == 0) {a[count++] = i;res *= i;if (res == n)break;}}cout << a[count - 1] << endl;return 0;
}

  在这种思路中,我们扩大了搜索的范围,同时我们增加了一个判断条件:如果发现这个数的质数了,就用一个res(初始为1)相乘,如果res == n了,说明我们已经找到了这个数的最大质因数~

   第三次提交的结果:

 再扩大一下搜索范围试试?

  第三次改进后的代码:

#include<iostream>
#include <iomanip>
#include<climits>
#include<cmath>using namespace std;int main()
{int a[100];int n, count = 0;cin >> n;int fact = n;int res = 1;for (int i = 2; i <= n/3; i++) {if (fact % i == 0) {a[count++] = i;res *= i;if (res == n)break;}}cout << a[count - 1] << endl;return 0;
}

第三次改进后的结果:

  可以看到搜索范围还是有问题的~

  大脑.exe已停止运行~

  感觉身体被掏空~

  又冥思苦想10分钟后,还是AC不掉这道题,没办法,看看大佬的题解吧,弱鸡瑟瑟发抖 T^T

  第四次提交的代码:

#include <iostream>
#include <cmath>using namespace std;int main()
{int n;                                 // 读取一个整数 ncin >> n;                               int largest_prime = 1;                 // 初始化 largest_prime 为 1for (int i = 2; i <= sqrt(n); i++) {    // 从 2 开始遍历到 sqrt(n) 之间的整数if (n % i == 0) {                   // 如果 n 能被 i 整除while (n % i == 0) {            // 不断地将 n 除以 i,直到 n 不能被 i 整除为止n /= i;}largest_prime = i;             // 更新 largest_prime 为当前的 i}}if (n > 1) {                           // 如果 n 大于 1,说明 n 本身就是一个素数largest_prime = n;                 // 将其赋值给 largest_prime}cout << largest_prime << endl;         // 输出 largest_primereturn 0;
}

  第四次提交的结果:

  是不是有点疑惑?为啥枚举到sqrt(n) ,就可以得出正确结果了呢?之前不是直接错了吗?

  这是因为在前面我们说过,这种方法只能找到最小的质因数,而不能找到最大的质因数,但是题目中明确的告诉我们这是两个质数相乘,所以不用再次判断这个数是否为质数,因此只要找到小的那个质数就可以直接通过相除找到最大的那个质因数~

以下是我当天AC这道题后写下的一些解释:

1.为什么可以直接用n除以较小的那一个质数就可以得到较大的那一个质数?
  质数本来就不可能再被分解,5和7不能被除它以外的数整除,所以5*7=35的两个因子只可能是5和7,不可能是其他因子,故两个质数的乘积分解也会是这两个质数,中间不可能会出现其他结果

2.为什么要枚举到<=sqrt?
  因为两个质数相乘的极端情况就是两个质数相等,比如5*5=25,此时需要在for循环里枚举到5
其他情况肯定就是一个质数大,另一个质数小,但是从for循环开始肯定是先枚举到较小的那一个质数,所以通过质数相乘原理就可以直接得出那一个较大的质数

什么,你跟我说你还不懂?那来看看我优化后的代码吧~

第四次改进后的代码:

#include<iostream>        // 包含输入输出流库
#include<cmath>           // 包含数学运算库using namespace std;int main()
{int n;                                 // 声明整数变量 n,用于存储输入的正整数cin >> n;                              // 输入正整数 nfor (int i = 2; i <= sqrt(n); i++) {   // 从 2 开始迭代直到 sqrt(n)if (n % i == 0) {                  // 如果 n 能被 i 整除n /= i;}                    }cout << n << endl;                     // 输出最大质数return 0;
}

第四次改进后的结果:

 可以看到,只要我们找到了最小的那个质因数,通过相除就可以直接找到最大的那个质因数,连while循环都不用,这道题就是一道纯纯的数学题~

又用了一坤时才写完,以后得提高一下水文(划掉)的速度了啊~

如果您觉得这篇文章对您有帮助的话,那不妨点个赞或者收藏呗,谢谢您~

如果您觉得我的文章有问题,请您私信我,我看到后就会及时改正,谢谢您!

感谢您的阅读!

这篇关于最小质因数 == 最大质因数,不等式秒了!的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/863048

相关文章

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 1102 uva 10397(最小生成树prim)

hdu 1102: 题意: 给一个邻接矩阵,给一些村庄间已经修的路,问最小生成树。 解析: 把已经修的路的权值改为0,套个prim()。 注意prim 最外层循坏为n-1。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstri

poj 3723 kruscal,反边取最大生成树。

题意: 需要征募女兵N人,男兵M人。 每征募一个人需要花费10000美元,但是如果已经招募的人中有一些关系亲密的人,那么可以少花一些钱。 给出若干的男女之间的1~9999之间的亲密关系度,征募某个人的费用是10000 - (已经征募的人中和自己的亲密度的最大值)。 要求通过适当的招募顺序使得征募所有人的费用最小。 解析: 先设想无向图,在征募某个人a时,如果使用了a和b之间的关系

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2175 最小费用最大流TLE

题意: 一条街上有n个大楼,坐标为xi,yi,bi个人在里面工作。 然后防空洞的坐标为pj,qj,可以容纳cj个人。 从大楼i中的人到防空洞j去避难所需的时间为 abs(xi - pi) + (yi - qi) + 1。 现在设计了一个避难计划,指定从大楼i到防空洞j避难的人数 eij。 判断如果按照原计划进行,所有人避难所用的时间总和是不是最小的。 若是,输出“OPETIMAL",若

poj 2135 有流量限制的最小费用最大流

题意: 农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。 农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。 约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。 如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。 解析: 如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。 但是现在要去要回

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta