首页 / 算法 / 【蓝桥杯】算法训练 素因子去重
【蓝桥杯】算法训练 素因子去重
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【蓝桥杯】算法训练 素因子去重,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3394字,纯文字阅读大概需要5分钟。
内容图文
![【蓝桥杯】算法训练 素因子去重](/upload/InfoBanner/zyjiaocheng/842/3c236cad5dad4f25a4881c29f1dc833e.jpg)
样例解释:n=1000=2^3*5*3,p=2*5=10 ? ? 题目还是很好理解的,一看到题,我的第一个思路就是先打印素数表,然后直接用整数的质因子分解来做,结果是耗时15ms,内存984.0KB。关于这两个过程可以戳以前的博客:埃氏筛法打印素数表? ?算术基本定理:整数质因子分解
1 #include <iostream> 2 using namespace std; 3 4 bool is_prime[10005]; 5 int prime[10005]; 6 void sieve(int n){ 7 int p = 0; 8 for(int i = 2; i <= n; i++) is_prime[i] = true; 9 for(int i = 2; i <= n; i++){ 10 if(is_prime[i]){ 11 prime[p++] = i; 12 for(int j = 2*i; j<=n; j+=i) is_prime[j] = false; 13 } 14 } 15 } 16 17 int main(int argc, char *argv[]) { 18 sieve(10005); 19 long long n, ans = 1; 20 cin>>n; 21 for(int i = 0;prime[i]*prime[i]<=n; i++){ 22 if(n % prime[i] == 0){ 23 ans *= prime[i]; 24 while(n % prime[i] == 0) n /= prime[i]; 25 } 26 } 27 ans *= n; 28 cout<<ans<<endl; 29 30 return 0; 31 }
后来发现自己把题目理解复杂了,下面给出我的第二个思路,耗时46ms,内存936.0KB。
1 #include <iostream> 2 using namespace std; 3 4 int main(int argc, char *argv[]) { 5 long long n, ans = 1; 6 cin>>n; 7 for(int k = 2; n != 1; k++){ 8 if(n % k == 0){ 9 ans = ans * k; 10 while(n % k == 0) n /= k; 11 } 12 } 13 cout<<ans<<endl; 14 15 return 0; 16 }
这个方法也很直接,从最小的质数2开始循环,判断当前的数k能不能整除n,如果可以就说明k是n的一个质因数,让ans乘上k,再让n除以k直到n不再包含k为止。每次循环k++。有个巧妙的地方在于,因为每次循环结束得到的新的n都已经不再包含上一个质因子k,所以下一次满足整除条件的k一定还是质数(有一点埃氏筛法的感觉)。比如取n=1000,它最小的质因子是2,在k=2的这一轮循环结束后,新的n为125,已经不再包含2,所以k=4时,n已经不再能被4整除,直接进入下一轮循环k=5。这一轮结束后,n=1,说明所有的质因子已经被找到,循环结束。
第三种方法是在网上看到的题解,我在循环那边优化了一下,也很简单直接,有一个素性判断的is_prime函数,然后直接循环判断质因子。下面是代码,耗时0ms,内存936.0KB。
1 #include <iostream> 2 using namespace std; 3 4 bool is_prime(long long n){ //判断n是否为素数 5 for(long long i = 2; i*i <=n; i++) 6 if(n%i ==0) return false; 7 return true; 8 } 9 10 int main(int argc, char *argv[]) { 11 long long n, m = 1; 12 cin>>n; 13 for(long long i = 2; i*i<=n; i++){ 14 if(n%i == 0 && is_prime(i)){ 15 m *= i; 16 while(n%i==0) n/=i; 17 } 18 } 19 m *= n; 20 cout<<m<<endl; 21 22 return 0; 23 }
最后一种也大同小异,用到了集合set元素,网上看到的题解。耗时46ms,内存932.0KB。(其实几种都差不多)
1 #include<iostream> 2 #include<set> 3 using namespace std; 4 5 set<int> s; 6 bool isPrime(long long n){ 7 for(int i=2; i*i <= n; i++) 8 if(n%i == 0) return false; 9 return true; 10 } 11 12 int main(){ 13 long long n, ans=1; 14 cin>>n; 15 for(int i=2; n!=1; i++) 16 if(n%i==0 && isPrime(i)){ 17 s.insert(i); 18 while(n%i==0) n/=i; 19 } 20 for(set<int>::iterator it=s.begin(); it!=s.end(); it++) 21 ans *= (*it); 22 cout<<ans<<endl; 23 24 return 0; 25 }
内容总结
以上是互联网集市为您收集整理的【蓝桥杯】算法训练 素因子去重全部内容,希望文章能够帮你解决【蓝桥杯】算法训练 素因子去重所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。