东莞网站建设及外包,qq推广链接,廊坊快速排名优化,h5制作模板免费下载作者#xff1a;指针不指南吗 专栏#xff1a;算法篇 #x1f43e;或许会很慢#xff0c;但是不可以停下#x1f43e; 文章目录1.GCDLCM2.判断素数(质数)3.分解质因子1.GCDLCM
最大公约数最小共倍数
欧几里得算法——高效
//最大公约数
int gcd(int x,i… 作者指针不指南吗 专栏算法篇 或许会很慢但是不可以停下 文章目录1.GCDLCM2.判断素数(质数)3.分解质因子1.GCDLCM
最大公约数最小共倍数
欧几里得算法——高效
//最大公约数
int gcd(int x,int y)
{return y?gcd(y,x%y):x;
}//最小公倍数
int lcm(int x,int y)
{return x*y/gcd(x,y);
}2.判断素数(质数)
孪生素数法——高效
分析过程如下 首先看一个关于质数分布的规律大于等于5的质数一定和6的倍数相邻。例如5和711和13,17和19等等 证明令x≥1将大于等于5的自然数表示如下 ······ 6x-16x6x16x26x36x46x56(x16(x1)1 ······ 可以看到不在6的倍数两侧即6x两侧的数为6x26x36x4由于2(3x1)3(2x1)2(3x2)所以它们一定不是素数再除去6x本身显然素数要出现只可能出现在6x的相邻两侧。这里要注意的一点是在6的倍数相邻两侧并不是一定就是质数。 此时用一个循环判断质数可以以6为单元快进i6加快判断速度。 原因是假如要判定的数为n则n必定是6x-1或6x1的形式对于循环中6i-16i6i1,6i26i36i4其中如果n能被 6i6i26i4整除则n至少得是一个偶数但是6x-1或6x1的形式明显是一个奇数故不成立另外如果n能被6i3整除则n至少能被3整除但是6x能被3整除故6x-1或6x1即n不可能被3整除故不成立。 综上循环中只需要考虑6i-1和6i1的情况即循环的步长可以定为6每次判断循环变量k和k2的情况即可 bool isprime(int n)
{if(n3) //特判几个较小的数return n1;if(n%6!1n%6!5) //不在6的倍数的两侧一定不是素数return 0;for(int i5;isqrt(n);i6) //判断在6的倍数的两侧的数是不是素数if(n%i0||n%(i2)0)return 0;return 1;
}3.分解质因子
直接看例题吧 题目 链接 AcWing 867. 分解质因数–解释代码注释 - AcWing 给定 n 个正整数 ai将每个数分解质因数并按照质因数从小到大的顺序输出每个质因数的底数和指数。 输入格式 第一行包含整数 n。 接下来 n 行每行包含一个正整数 ai。 输出格式 对于每个正整数 ai按照从小到大的顺序输出其分解质因数后每个质因数的底数和指数每个底数和指数占一行。 每个正整数的质因数全部输出完毕后输出一个空行。 数据范围 1≤n≤100, 2≤ai≤2×10910^9109 输入样例 2
6
8输出样例 2 1
3 12 3分析 x 的质因子最多只包含一个大于 根号x 的质数。如果有两个这两个因子的乘积就会大于 x矛盾。i 从 2 遍历到 根号x。 用 x / i如果余数为 0则 i 是一个质因子。s 表示质因子 i 的指数x / i 为 0则 s x x / i 。最后检查是否有大于 根号x 的质因子如果有输出。 代码实现 #includebits/stdc.h
using namespace std;void divide(int x)
{for (int i 2; i x / i; i )//i x / i:防止越界速度大于 i sqrt(x)if (x % i 0)//i为底数{int s 0;//s为指数while (x % i 0) x / i, s ;cout i s endl;//输出}if (x 1) cout x 1 endl;//如果x还有剩余单独处理cout endl;
}int main()
{int n;cin n;while (n -- ){int x;cin x;divide(x);}return 0;
}
