试题算法训练素因子去重

最新推荐文章于 2022-03-27 19:35:34 发布

xiao黄

最新推荐文章于 2022-03-27 19:35:34 发布

阅读量413

点赞数 1

分类专栏：蓝桥杯文章标签： python 蓝桥杯

本文链接：https://blog.csdn.net/Python_Matlab/article/details/104949663

版权

蓝桥杯专栏收录该内容

69 篇文章

订阅专栏

代码已经更新，通过了测试，思路是加入一个素数判断函数，解决了超时的问题。
注意：题目中的样例解释有误，正确的是：n=1000=2^3 * 5^3，p=2*5=10
思路：利用while循环，对每个i除到不能再除的情况下，把i相乘即可，代码如下。
附：此代码在蓝桥杯测试系统只有70的正确率，原因是超时了，不知如何改正，若有大佬看到这篇文章，望不吝指教。

资源限制
时间限制：1.0s   内存限制：256.0MB
问题描述
　　给定一个正整数n，求一个正整数p，满足p仅包含n的所有素因子，且每个素因子的次数不大于1
输入格式
　　一个整数，表示n
输出格式
　　输出一行，包含一个整数p。
样例输入
1000
样例输出
10
数据规模和约定
　　n<=10^12
　　样例解释：n=1000=2^3*5*3，p=2*5=10

n = int(input())
if n >0 and n <=10**12:
    s = 1
    for i in range(2,n):
        if n%i==0:
            s *= i
            while n%i==0:
                n //=i
    print(s)

代码更新：

import math
def isprime(n):
    '''
    判断是不是素数，是就返回True，否就返回False
    '''
    if n < 2: 
        return False
    for i in range(2,int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

n = int(input())
p = 1
for i in range(2,n+1):
    if isprime(n):
        p *= n
        break
    if n%i==0:
        while n%i==0:
            n //= i
        p *= i
print(p)