质因数分解题如何优化？
本帖不欢迎ChatGPT.本帖不欢迎ChatGPT,我已经问过他了，他也不靠谱
题目https://www.luogu.com.cn/problem/P1619
记录https://www.luogu.com.cn/record/123079697
疯狂TLE
我调试了一下，发现xxs算法筛4e8的素数本身就要500ms左右，那留给分解的时间就很少了。
所以这个程序应该怎么优化呢？可以从筛法（虽然好像没法再优化了）或者质因数分解的角度来去优化。
我反正已经没办法了。
源代码
#include <cstdio>
#include <cctype>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAXN 40000000
vector<int>prime;
bool is_prime;
inline void itoa(int x,char * str)
{
int t=x,i;
char temp={'\0'};
for(i=0;t>0;i++)
{
temp=t%10+'0';
t/=10;
}
for(int j=i-1;j>-1;j--)
{
str=temp;
}
str='\0';
}
inline int read(void)
{
int x=0;
char ch,flag=0;
while((ch=getchar())!='\n')
{
if(isdigit(ch))
{
flag=1;
x=(x<<3)+(x<<1)+(ch^48);
}
if(x>40000000)
{
flag=2;
break;
}//inf
}
if(flag==2)
{
while(1)
{
if(getchar()=='\n')break;
}
return -1;
}
if(!flag)return -2;//NaN
return x;
}
inline string bzfj(int x)
{
string ans;
char str={'\0'};
int cnt,t=x,p=0;
while(t>1)
{
cnt=0;
while(t%prime==0)
{
t/=prime;
cnt++;
}
if(cnt)
{
itoa(prime,str);
ans+=str;
ans+="^";
itoa(cnt,str);
ans+=str;
ans+="*";
}
p++;
}
ans.pop_back();
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int cnt=0;
int n=MAXN;
memset(is_prime,true,sizeof(is_prime));
is_prime=false;
is_prime=false;
for(int i=2;i<=n;i++)// init vector
{
if(is_prime)
{
prime.push_back(i);
cnt++;
}
for(int j =0;j<cnt and i*prime<=n;j++)
{
is_prime]=false;
if(i%prime==0)break;
}
}
int x;
while(1)
{
cout<<"Enter the number="<<endl;
x=read();
if(x==-1)//inf
cout<<"Prime? No!\nThe number is too large!\n\n";
else if(x==-2)//NaN
return 0;
else
{
if(x<2)
{
cout<<"Prime? No!"<<endl<<endl;
continue;
}
if(is_prime)
{
cout<<"Prime? Yes!\n\n";
}
else
{
cout<<"Prime? No!\n"<<x<<"="<<bzfj(x)<<endl<<endl;
}
}
}
}
@zhangjinxuan @Ewan-Ahiouy @sfqxx @高山 @元豪
谢谢了！ 我是不会让GPT回答的 这个程序可以从两个方面进行优化：筛法和质因数分解。
首先，关于筛法，你使用的是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 发表于 2023-8-28 16:11
这本来是一到篮题，你直接模拟试一试
这不就是模拟吗？ 这个题解你看的懂吗？分解质因数
int fj(unsigned long long a)//事实上没必要那么大
{ long long b=a,k=0;
for(int i=2;i<=a;i++){
while(a%i==0){
a/=i;ss++;
}
}printf("\n%lld=",b);
for(long long i=2;i<=b/2&&i<10000000;i++){//严防越界
//40000000以下的数因数不会太大
if(ss&&k==0){
printf("%lld^%d",i,ss);k=1;//注意格式
}
else if(ss)printf("*%lld^%d",i,ss);
}
for(int i=0;i<10000000;i++)ss=0;
return 0;
} sfqxx 发表于 2023-8-29 13:38
这个题解你看的懂吗？分解质因数
我就是这种分解方式。
但是我的线性筛耗了500ms What????????????????????????
看了题解以后发现
原来不用先存好质数表是吧？？？ 不用xxs能过？
页:
[1]