素因子去重降底时间复杂度
本帖最后由 会飞的鱼 于 2019-4-10 13:48 编辑蓝桥杯素因子去重问题问题描述 给定一个正整数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;
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=i;
k++;
}
}
}
for(i=0;i<k;i++)
{
p*=a;
}
cout<<p;
return0;
}
然后我仔细检查了以下发现可以直接降底外层循环量，来降底时间复杂度。然后修改代码如下：#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;
cin>>n;
for(i=2; i<=sqrt(n); i++)//降底外层循环次数，直接开根号
{
if(n%i==0)
{
if(fun(i))
{
a=i;
k++;
}
if(fun(n/i))//因外层循环开根号之后部分数据无法计算，所以此处解决特殊情况，例如数据533=13*41
{
a=n/i;
k++;
}
}
}
for(i=0; i<k; i++)//计算乘积
{
//cout<<a<<endl;
p*=a;
}
cout<<p;
return0;
}
成功通过！ 这教程对纯小白不友好{:7_198:} Shin 发表于 2019-3-7 16:42
本教程纯小白先绕过{:3_50:} Gu-f 发表于 2019-3-7 17:14
{:7_194:} Shin 发表于 2019-3-7 17:17
关键部分请看代码注释部分
页:
[1]