质因数分解题如何优化？

额外减小

本帖不欢迎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. 
    
13. inline void itoa(int x,char * str)
    
14. {
    
15.     int t=x,i;
    
16.     char temp[10]={'\0'};
    
17.     for(i=0;t>0;i++)
    
18.     {
    
19.         temp[i]=t%10+'0';
    
20.         t/=10;
    
21.     }
    
22.     for(int j=i-1;j>-1;j--)
    
23.     {
    
24.         str[i-j-1]=temp[j];
    
25.     }
    
26.     str[i]='\0';
    
27. }
    
28. 
    
29. inline int read(void)
    
30. {
    
31.     int x=0;
    
32.     char ch,flag=0;
    
33.     while((ch=getchar())!='\n')
    
34.     {
    
35.         if(isdigit(ch))
    
36.         {
    
37.             flag=1;
    
38.             x=(x<<3)+(x<<1)+(ch^48);
    
39.         }
    
40.         if(x>40000000)
    
41.         {
    
42.             flag=2;
    
43.             break;
    
44.         }//inf
    
45.     }
    
46.     if(flag==2)
    
47.     {
    
48.         while(1)
    
49.         {
    
50.             if(getchar()=='\n')break;
    
51.             
    
52.         }
    
53.         return -1;
    
54.     }
    
55.     if(!flag)return -2;//NaN
    
56.     return x;
    
57.    
    
58. }
    
59. 
    
60. inline string bzfj(int x)
    
61. {
    
62.     string ans;
    
63.     char str[14]={'\0'};
    
64.     int cnt,t=x,p=0;
    
65.     while(t>1)
    
66.     {
    
67.         cnt=0;
    
68.         while(t%prime[p]==0)
    
69.         {
    
70.             t/=prime[p];
    
71.             cnt++;
    
72.         }
    
73.         if(cnt)
    
74.         {
    
75.             itoa(prime[p],str);
    
76.             ans+=str;
    
77.             ans+="^";
    
78.             itoa(cnt,str);
    
79.             ans+=str;
    
80.             ans+="*";
    
81.         }
    
82.         p++;
    
83.     }
    
84.     ans.pop_back();
    
85.    
    
86.     return ans;
    
87. }
    
88. 
    
89. int main()
    
90. {
    
91.     ios::sync_with_stdio(false);
    
92.     cin.tie(0),cout.tie(0);
    
93.     int cnt=0;
    
94.         int n=MAXN;
    
95.         memset(is_prime,true,sizeof(is_prime));
    
96.     is_prime[0]=false;
    
97.     is_prime[1]=false;
    
98.     for(int i=2;i<=n;i++)// init vector
    
99.     {
    
100.         if(is_prime[i])
     
101.         {
     
102.             prime.push_back(i);
     
103.             cnt++;
     
104.         }
     
105.         for(int j =0;j<cnt and i*prime[j]<=n;j++)
     
106.         {
     
107.             is_prime[i*prime[j]]=false;
     
108.             if(i%prime[j]==0)break;
     
109.         }
     
110.     }
     
111.     int x;
     
112.     while(1)
     
113.     {
     
114.         cout<<"Enter the number="<<endl;
     
115.         x=read();
     
116.         if(x==-1)//inf
     
117.         cout<<"Prime? No!\nThe number is too large!\n\n";
     
118.         else if(x==-2)//NaN
     
119.         return 0;
     
120.         else
     
121.         {
     
122.             if(x<2)
     
123.             {
     
124.                 cout<<"Prime? No!"<<endl<<endl;
     
125.                 continue;
     
126.             }
     
127.             if(is_prime[x])
     
128.             {
     
129.                 cout<<"Prime? Yes!\n\n";
     
130.             }
     
131.             else
     
132.             {
     
133.                
     
134.                 cout<<"Prime? No!\n"<<x<<"="<<bzfj(x)<<endl<<endl;
     
135.             }
     
136.         }
     
137.     }
     
138.    
     
139. }

复制代码

@zhangjinxuan @Ewan-Ahiouy @sfqxx @高山 @元豪
谢谢了！

陶远航

我是不会让GPT回答的

isdkz

这个程序可以从两个方面进行优化：筛法和质因数分解。

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

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

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

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

希望这些优化措施能帮助你提高程序的性能。如果你有任何疑问，请随时向我提问。

额外减小

isdkz 发表于 2023-8-28 14:26
这个程序可以从两个方面进行优化：筛法和质因数分解。

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

就说不靠谱。xxs已经最优了。stringstream常数反而大。你叫我不存素数？那我保证10个点全部变黑

sfqxx

这本来是一到篮题，你直接模拟试一试

额外减小

sfqxx 发表于 2023-8-28 16:11
这本来是一到篮题，你直接模拟试一试

这不就是模拟吗？

sfqxx

这个题解你看的懂吗？分解质因数

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. }

复制代码

额外减小

sfqxx 发表于 2023-8-29 13:38
这个题解你看的懂吗？分解质因数

我就是这种分解方式。
但是我的线性筛耗了500ms

额外减小

What????????????????????????

看了题解以后发现
原来不用先存好质数表是吧？？？

额外减小

不用xxs能过？