素因子去重降底时间复杂度

Gu-f

蓝桥杯素因子去重问题

问题描述

　　给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1

输入格式

　　一个整数，表示n

输出格式

　　输出一行，包含一个整数p。

样例输入

1000

样例输出

10

话不多说，直接上代码

下面是我第一次写的代码，但是提交上去侯运行超时了，只通过了部分数据，剩余数据超时。

#include <iostream>
#include<cmath>
#include<string>
using namespace std;
int main()
{
    long long int n,i,j,k=0,p=1;
    int a[100001];
    cin>>n;
    for(i=2;i<=n;i++)
    {
        int flag=1;
        if(n%i==0)
        {
            for(j=2;j<=sqrt(i);j++)
            {
                if(i%j==0)
                {
                    flag=0;
                    break;
                }
            }
            if(flag)
            {
                a[k]=i;
                k++;
            }
        }
    }
    for(i=0;i<k;i++)
    {
       p*=a[i];
    }
    cout<<p;
    return  0;
}

然后我仔细检查了以下发现可以直接降底外层循环量，来降底时间复杂度。

然后修改代码如下：

#include <iostream>
#include<cmath>
#include<string>
using namespace std;
int fun(long long int i)//判断素数
{
    long long int j;
    for(j=2; j<=sqrt(i); j++)
    {
        if(i%j==0)
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    long long int n,i,k=0,p=1;
    int a[100001];
    cin>>n;
    for(i=2; i<=sqrt(n); i++)//降底外层循环次数，直接开根号
    {
        if(n%i==0)
        {
            if(fun(i))
            {

                a[k]=i;
                k++;
            }
            if(fun(n/i))//因外层循环开根号之后部分数据无法计算，所以此处解决特殊情况，例如数据533=13*41
            {
                a[k]=n/i;
                k++;
            }
        }
    }
    for(i=0; i<k; i++)//计算乘积
    {
        //cout<<a[i]<<endl;
        p*=a[i];
    }
    cout<<p;
    return  0;
}

成功通过！

roger

这教程对纯小白不友好

Gu-f

Shin 发表于 2019-3-7 16:42

本教程纯小白先绕过{:3_50:}

roger

Gu-f 发表于 2019-3-7 17:14

Gu-f

Shin 发表于 2019-3-7 17:17

关键部分请看代码注释部分