【Leetcode刷题Python】最小因子问题

2022年秋招京东算法工程师笔试题
2022-9-3

1 题目

1、最小因子问题

小红拿到一个正整数n，他希望找到n的一个最小因子p，满足p*p>n

案例：

输入

2

36

37

输出
9

37

2 python实现

def low_fac(n):
    k = n
    for i in range(1,n+1):
        if n%i==0 and i*i>k:
            print(int(i))
N = int(input())
for _ in range(N):
    j = int(input())
    low_fac(j)

以上算法超时

优化后的方法

import math
def low_fac(n):
    ans = []
    for i in range(1,int(math.sqrt(n))):
        if n%i==0:
            if i*i>n:
                ans.append(i)
            t = int(n/i)
            if t!=i and t*t>n:
                ans.append(t)
    return min(ans)       

N = int(input())
for _ in range(N):
    j = int(input())
    print(low_fac(j))