鱼C论坛

 找回密码
 立即注册
查看: 1844|回复: 9

质因数分解题如何优化?

[复制链接]
发表于 2023-8-28 14:25:22 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖不欢迎ChatGPT.

本帖不欢迎ChatGPT,我已经问过他了,他也不靠谱

题目  https://www.luogu.com.cn/problem/P1619
记录  https://www.luogu.com.cn/record/123079697
疯狂TLE

我调试了一下,发现xxs算法筛4e8的素数本身就要500ms左右,那留给分解的时间就很少了。
所以这个程序应该怎么优化呢?可以从筛法(虽然好像没法再优化了)或者质因数分解的角度来去优化。
我反正已经没办法了。
源代码
  1. #include <cstdio>
  2. #include <cctype>
  3. #include <vector>
  4. #include <cstring>
  5. #include <string>
  6. #include <algorithm>
  7. #include <iostream>
  8. using namespace std;
  9. #define MAXN 40000000
  10. vector<int>prime;
  11. bool is_prime[MAXN];

  12. inline void itoa(int x,char * str)
  13. {
  14.     int t=x,i;
  15.     char temp[10]={'\0'};
  16.     for(i=0;t>0;i++)
  17.     {
  18.         temp[i]=t%10+'0';
  19.         t/=10;
  20.     }
  21.     for(int j=i-1;j>-1;j--)
  22.     {
  23.         str[i-j-1]=temp[j];
  24.     }
  25.     str[i]='\0';
  26. }

  27. inline int read(void)
  28. {
  29.     int x=0;
  30.     char ch,flag=0;
  31.     while((ch=getchar())!='\n')
  32.     {
  33.         if(isdigit(ch))
  34.         {
  35.             flag=1;
  36.             x=(x<<3)+(x<<1)+(ch^48);
  37.         }
  38.         if(x>40000000)
  39.         {
  40.             flag=2;
  41.             break;
  42.         }//inf
  43.     }
  44.     if(flag==2)
  45.     {
  46.         while(1)
  47.         {
  48.             if(getchar()=='\n')break;
  49.             
  50.         }
  51.         return -1;
  52.     }
  53.     if(!flag)return -2;//NaN
  54.     return x;
  55.    
  56. }

  57. inline string bzfj(int x)
  58. {
  59.     string ans;
  60.     char str[14]={'\0'};
  61.     int cnt,t=x,p=0;
  62.     while(t>1)
  63.     {
  64.         cnt=0;
  65.         while(t%prime[p]==0)
  66.         {
  67.             t/=prime[p];
  68.             cnt++;
  69.         }
  70.         if(cnt)
  71.         {
  72.             itoa(prime[p],str);
  73.             ans+=str;
  74.             ans+="^";
  75.             itoa(cnt,str);
  76.             ans+=str;
  77.             ans+="*";
  78.         }
  79.         p++;
  80.     }
  81.     ans.pop_back();
  82.    
  83.     return ans;
  84. }

  85. int main()
  86. {
  87.     ios::sync_with_stdio(false);
  88.     cin.tie(0),cout.tie(0);
  89.     int cnt=0;
  90.         int n=MAXN;
  91.         memset(is_prime,true,sizeof(is_prime));
  92.     is_prime[0]=false;
  93.     is_prime[1]=false;
  94.     for(int i=2;i<=n;i++)// init vector
  95.     {
  96.         if(is_prime[i])
  97.         {
  98.             prime.push_back(i);
  99.             cnt++;
  100.         }
  101.         for(int j =0;j<cnt and i*prime[j]<=n;j++)
  102.         {
  103.             is_prime[i*prime[j]]=false;
  104.             if(i%prime[j]==0)break;
  105.         }
  106.     }
  107.     int x;
  108.     while(1)
  109.     {
  110.         cout<<"Enter the number="<<endl;
  111.         x=read();
  112.         if(x==-1)//inf
  113.         cout<<"Prime? No!\nThe number is too large!\n\n";
  114.         else if(x==-2)//NaN
  115.         return 0;
  116.         else
  117.         {
  118.             if(x<2)
  119.             {
  120.                 cout<<"Prime? No!"<<endl<<endl;
  121.                 continue;
  122.             }
  123.             if(is_prime[x])
  124.             {
  125.                 cout<<"Prime? Yes!\n\n";
  126.             }
  127.             else
  128.             {
  129.                
  130.                 cout<<"Prime? No!\n"<<x<<"="<<bzfj(x)<<endl<<endl;
  131.             }
  132.         }
  133.     }
  134.    
  135. }
复制代码

@zhangjinxuan @Ewan-Ahiouy @sfqxx @高山 @元豪
谢谢了!
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2023-8-28 14:26:03 | 显示全部楼层
我是不会让GPT回答的

评分

参与人数 1鱼币 +2 收起 理由
额外减小 + 2 鱼C有你更精彩^_^

查看全部评分

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-28 14:26:15 | 显示全部楼层
这个程序可以从两个方面进行优化:筛法和质因数分解。

首先,关于筛法,你使用的是xxs算法,它的时间复杂度是O(nloglogn),对于4e8的素数筛选来说,确实会花费一定的时间。如果你想要更快的筛法,可以考虑使用更高效的筛法,如埃拉托斯特尼筛法(Sieve of Eratosthenes)或线性筛法(Linear Sieve)。这些算法的时间复杂度都是O(n),可以更快地生成素数数组。

其次,关于质因数分解,你的代码使用了一个自定义的itoa函数来将整数转换为字符串。这个函数在循环中被频繁调用,可能会造成一定的性能损失。你可以考虑使用更高效的方法来进行质因数分解和字符串拼接,例如使用stringstream来构建字符串,或者直接使用字符串拼接操作符+。

另外,你的代码中使用了vector来存储素数数组,这会占用额外的内存空间。如果你只需要判断一个数是否为素数,可以考虑使用bitset来进行标记,这样可以更节省内存。

总结一下,你可以尝试以下优化措施:
1. 使用更高效的筛法,如埃拉托斯特尼筛法或线性筛法。
2. 优化质因数分解部分的字符串拼接操作,考虑使用stringstream或字符串拼接操作符+。
3. 考虑使用bitset来存储素数数组,以节省内存。

希望这些优化措施能帮助你提高程序的性能。如果你有任何疑问,请随时向我提问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-28 14:28:32 | 显示全部楼层
isdkz 发表于 2023-8-28 14:26
这个程序可以从两个方面进行优化:筛法和质因数分解。

首先,关于筛法,你使用的是xxs算法,它的时间复 ...

就说不靠谱。xxs已经最优了。stringstream常数反而大。你叫我不存素数?那我保证10个点全部变黑
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-28 16:11:45 From FishC Mobile | 显示全部楼层
这本来是一到篮题,你直接模拟试一试
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-28 19:08:57 | 显示全部楼层
sfqxx 发表于 2023-8-28 16:11
这本来是一到篮题,你直接模拟试一试

这不就是模拟吗?
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-8-29 13:38:48 | 显示全部楼层
这个题解你看的懂吗?分解质因数
  1. int fj(unsigned long long a)//事实上没必要那么大
  2. { long long b=a,k=0;
  3.         for(int i=2;i<=a;i++){
  4.                 while(a%i==0){
  5.                         a/=i;ss[i]++;
  6.                 }
  7.         }printf("\n%lld=",b);
  8.         for(long long i=2;i<=b/2&&i<10000000;i++){//严防越界
  9.     //40000000以下的数因数不会太大
  10.                 if(ss[i]&&k==0){
  11.                         printf("%lld^%d",i,ss[i]);k=1;//注意格式
  12.                 }
  13.                 else if(ss[i])printf("*%lld^%d",i,ss[i]);
  14.         }
  15.         for(int i=0;i<10000000;i++)ss[i]=0;
  16.         return 0;
  17. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-29 14:08:59 | 显示全部楼层
sfqxx 发表于 2023-8-29 13:38
这个题解你看的懂吗?分解质因数

我就是这种分解方式。
但是我的线性筛耗了500ms
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-29 14:30:41 | 显示全部楼层
What????????????????????????

看了题解以后发现
原来不用先存好质数表是吧???
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-8-29 14:32:27 | 显示全部楼层
不用xxs能过?
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-6-10 00:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表