蓝桥杯|算法训练素因子去重蓝桥杯|c++|数论

题目链接

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

分析：之前写了需要判断是素数（虽然通过了）；后面发现是不需要判断的。因为当你每次去掉一个素因子后，这个因子的倍数就会不存在了。这个和素数筛选差不多，只不过素数筛选是标记，这里是删除。
因为i从最小的质因子2开始并且每次循环结束得到的新的n都已经不再包含上一个质因子i，所以下一次满足整除条件的i(能被n整除的i)一定还是质数.（如n=60. 当 i = 2 时，n变成了15，当i = 4时（i = 3是质数不用考虑），n的因子是不包含2的，所以更不可能包含4，如此类推.....）

#include using namespace std; int main(int argc, char** argv) { long long n, p = 1; cin>> n; for(long long i = 2; i*i <= n ; i++){ if(n%i == 0 ){ p *= i; while( n%i == 0 ) n /= i; } } cout<< p*n<< '\n'; return 0; }

输入格式
一个整数，表示n
输出格式
输出一行，包含一个整数p。
样例输入
1000
样例输出
10
数据规模和约定
【蓝桥杯|算法训练素因子去重】n<=10^12
样例解释：n=1000=2^3*5*3，p=2*5=10