网站内容规范,网站技术维护费,没有网站做推广,wordpress调用当前页面链接机试中存在部分涉及到较复杂数字的问题#xff0c;这是编码的基本功#xff0c;各位一定要得心应手。 目录
一.最大公约数和最小公倍数
1.最大公约数
2.最小公倍数
二.素数
1.判断指定数
2.输出所有素数
3.精进不休——埃拉托斯特尼筛法
4.达到更优#xff01;——…机试中存在部分涉及到较复杂数字的问题这是编码的基本功各位一定要得心应手。 目录
一.最大公约数和最小公倍数
1.最大公约数
2.最小公倍数
二.素数
1.判断指定数
2.输出所有素数
3.精进不休——埃拉托斯特尼筛法
4.达到更优——欧拉筛法 一.最大公约数和最小公倍数
初学就开始的老生常谈比较基础大一期末考试和普通学校考研的难度一定不要掉以轻心。
1.最大公约数
这里我们用欧几里得算法来实现——其实也就是初中学过的辗转相除法没什么难度~
int gcb(int x,int y)
{if(xy) //保证前者更大一些 {int tempx;xy;ytemp;}while(y!0){int tempy;yx%y;xtemp;} return x;
}
2.最小公倍数
设最大公约数是z则x和y的最小公倍数就是x*y/z这个公式也是小学知识不要忘了要是考试的时候真不小心忘了就用暴力枚举吧从x和y大的一个开始直到第一个可以同时整除x和y的元素即为最小公倍数~
int main() {int x0,y0; cout请输入两个数;cinxy;cout最大公约数是gcb(x,y)endl;cout最小公倍数是(x*y)/gcb(x,y)endl;}
没什么问题 二.素数
1.判断指定数 常规的暴力枚举复杂度度为O(N)其实有更为简洁的办法——即对目标数开根号比如对于16来说2就是其的一个约数但是16/2也是其一个约数显然我们并不需要枚举到8——因为对于一个数来说既然能整除那么约数肯定是成对出现的因此其中一个肯定比16开根号小另一个则肯定大所以我们只需要枚举到4也就是开根号就能判断目标数字是否为素数~
bool IsPrime(int x)
{int tempsqrt(x);for(int i2;itemp;i)if(x%i0)return false;return true;
}
非常简单不再赘述~
2.输出所有素数
上面函数已经有了我们只需要枚举范围内的元素并调用函数即可输出全部的素数
int main() {int x0;cout请输入查询的最大值; cinx;int count0;for(int i1;ix;i){if(IsPrime(i)){couti ;count;}if(count5){coutendl;count0;}}
}
没什么bugcount是为了输出更美观附加的 3.精进不休——埃拉托斯特尼筛法 不妨这样思考一下假设2是素数的话那么他的倍数——4/6/8/10等等一切可以整除2的数——是不是都不是素数因此当我们找到一个素数时如果将他的全部倍数都标记为合数岂不是大大增加了效率。事实上这就是埃拉托斯特尼筛法其复杂度为LogN的平方复杂度还要小于前面的N*根号N代码如下
#include iostream
#include vector
#include cmathusing namespace std;void Eratos(int x)
{vectorint Num,answer;Num.push_back(-1);//统一vector中的数字与下标 for(int i1;ix;i)Num.push_back(0); //初始化数组,如果下标i是0则代表i是素数for(int i2;ix;i){if(Num[i]0){answer.push_back(i);for(int jii;jx;ji)//如果i是素数则i所有的倍数都不是素数 Num[j]1; } } for(int k0;kanswer.size()-1;k)coutanswer[k] ;
}int main() {int x0;cout请输入查询的最大值; cinx;Eratos(x);
}
没什么问题 诸位不妨仔细品味一下这个筛选的方法及其实现——是不是又有散列又有二分的思想何其妙哉~
4.达到更优——欧拉筛法 实际上埃拉托斯特尼筛法还是有其优化的余地比如6、10两个数字按照其规则这两个数在2的时候已经判断不是素数了但是当枚举到3和5的时候实际上还要再判断一次 因此不妨保证——每个合数只是被自己最小的质因数找到这样就避免了重复的筛选步骤。为了防止大家晕这里修改一下埃式筛的代码
#include iostream
#include vector
#include cmathusing namespace std;void Eratos(int x)
{int times0;int count0;//记录当前素数的个数vectorint answer;//存放所有的素数vectorint Num;//标记Num.push_back(0);//统一下标和数字大小 for(int i1;ix;i)Num.push_back(0);for(int i2;ix;i){if(!Num[i]){answer.push_back(i);count;}for(int j0;jcount;j){if(i*answer[j]x)break;int tempi*answer[j];Num[temp]1;times;
// if (i % answer[j] 0)
// break;}} for(int k0;kanswer.size()-1;k)coutanswer[k] ;coutendl;cout共标记了times次;
} int main() {int x0;cout请输入查询的最大值; cinx;Eratos(x);
}
我们来测试一下100可以发现标记合数的步骤一共执行了104次 我们仔细回溯一下如上代码的运行流程
当i2时是素数因此放到answer数组中接下来遍历answer数组2*24因此4肯定不是素数标记为合数接下来i3是素数因此放到answer数组中接下来遍历answer3*26,3*39因此6和9均被标记为合数接下来i4不是素数直接遍历answer2*48,3*412,8应该被标记为合数但是对于12其最小约数是2因此应该由6*2来标记所以此刻应该直接跳过
因此就有了有欧拉的写法
void Eratos(int x)
{int times0;int count0;//记录当前素数的个数vectorint answer;//存放所有的素数vectorint Num;//标记Num.push_back(0);//统一下标和数字大小 for(int i1;ix;i)Num.push_back(0);for(int i2;ix;i){if(!Num[i]){answer.push_back(i);count;}for(int j0;jcount;j){if(i*answer[j]x)break;int tempi*answer[j];Num[temp]1;times;if (i % answer[j] 0)break;}} for(int k0;kanswer.size()-1;k)coutanswer[k] ;coutendl;cout共标记了times次;
}
核心在于这个大家自行品味妙处——对于上面来说因为4已经遇到了最小质因数2因此应该直接跳出循环 运行100以内的素数只执行了74次! 我们再来拿1000测试一下 埃氏筛用了1400多次而欧式筛只用了800多次高低立判 今天就先总结到这希望如上的素数搜索对各位思考算法的意义有所启发——当人力无法计算庞大的运算量时计算机应运而生而计算机由于计算方式的不同效率也不尽相同。我们追求高效简洁的算法因为越低的耗时标志着越高的生产力——而相信各位都学过马克思主义基本原理社会变革的根本原因是生产力的发展~博主有幸拜读过《人月神话》相信大家都清楚【银弹】对于软件工程的意义。或许对于银弹的不懈追求正是人类能够进化的原因~
