质因数分解题如何优化？

额外减小

本帖不欢迎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[MAXN];

inline void itoa(int x,char * str)
{
    int t=x,i;
    char temp[10]={'\0'};
    for(i=0;t>0;i++)
    {
        temp[i]=t%10+'0';
        t/=10;
    }
    for(int j=i-1;j>-1;j--)
    {
        str[i-j-1]=temp[j];
    }
    str[i]='\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[14]={'\0'};
    int cnt,t=x,p=0;
    while(t>1)
    {
        cnt=0;
        while(t%prime[p]==0)
        {
            t/=prime[p];
            cnt++;
        }
        if(cnt)
        {
            itoa(prime[p],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[0]=false;
    is_prime[1]=false;
    for(int i=2;i<=n;i++)// init vector
    {
        if(is_prime[i])
        {
            prime.push_back(i);
            cnt++;
        }
        for(int j =0;j<cnt and i*prime[j]<=n;j++)
        {
            is_prime[i*prime[j]]=false;
            if(i%prime[j]==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[x])
            {
                cout<<"Prime? Yes!\n\n";
            }
            else
            {
                
                cout<<"Prime? No!\n"<<x<<"="<<bzfj(x)<<endl<<endl;
            }
        }
    }
    
}

@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

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

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[i]++;
                }
        }printf("\n%lld=",b);
        for(long long i=2;i<=b/2&&i<10000000;i++){//严防越界
    //40000000以下的数因数不会太大
                if(ss[i]&&k==0){
                        printf("%lld^%d",i,ss[i]);k=1;//注意格式
                }
                else if(ss[i])printf("*%lld^%d",i,ss[i]);
        }
        for(int i=0;i<10000000;i++)ss[i]=0;
        return 0;
}

额外减小

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

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

额外减小

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

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

额外减小

不用xxs能过？