基础算法题——素因子去重

梦里梦外; 2023-07-15 09:20 8阅读 0赞

#### 素因子去重题目 ####

问题描述  
　　给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1  
输入格式  
　　一个整数，表示n  
输出格式  
　　输出一行，包含一个整数p。  
样例输入  
1000  
样例输出  
10  
数据规模和约定  
　　n<=10^12  
　　样例解释：n=1000=23 \* 53，p=2 \* 5=10

--------------------

**思路一**：通过筛选法将2~1012中的素数求出，再通过枚举素数的方式判断素数是否为n的因数，将是n的素因数（不重复）累乘，即可得到答案。该思路的复杂度为O(n)。这个思路没错，但是数据规模和约定中写明n<=1012，假设n==1012时，程序会出现运行时间过长的情况。

--------------------

通过观察题目，我们了解到p为n的素因数乘积，且每个素因子的次数不大于1。  
考虑最糟糕的情况，假设1012>=n>=1011，同时n又恰好等于为106规模上的素数与105规模上的素数（不重复）的乘积，那么我们只要判断0~106内的素数的情况就能够判断出p，得出思路二。

**思路二**：筛选法将2~106中的素数求出，再通过枚举素数的方式判断素数是否为n的因数，将是n的素因数累乘，即可得到答案。该思路的复杂度为O(n1/2)。满足题目运行时间条件。

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll n, p;
    bool judge[1000010];
    ll sz[100];
    void ss(void)//筛选法
    { 
    	for(ll i=2; i<=1000000; i++)
    	{ 
    		if(judge[i]==false)
    		{ 
    			for(ll j=2; j*i<=1000000; j++)
    				judge[j*i]=true;
    		}
    	}
    }
    
    int main()
    { 
    	cin>>n;
    	ss();
    	ll j=0, sum=1, i;
    	for(i=2; i<=n; i++)
    	{ 
    		if(judge[i]==false&&n%i==0)
    		{ 
    			while(n%i==0)//去重
    				n=n/i;
    			sum*=i;
    		}
    		if(i==1000000) break;
    	}
    	cout<<n*sum;
    	return 0;
    }

这代码条件恰好卡在n<=1012这个条件。  
如果我们输入大于1012的数的话，由于p<=106，该代码就可能判断不出p的真实大小。

--------------------

**验证**一下我们的想法：  
当n>1012  
假设n=96714764456322（素数9834367\*非素数9834366），很明显此时n不是素数。  
但是输出程序后的结果如下：  
![验证][20200316145111215.png]  
p输出n==96714764456322。  
按照思路：在n为素数和非素数的乘积条件下，p一定满足：p<n。  
这表明p输出的答案是有误的。

希望能够将自己的一些学习经验分享给有需要的人。  
我是小郑，一个坚持不懈的小白。

[20200316145111215.png]: /images/20230528/c4f4418c96b445579e5809c96b279564.png