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

1 题目

1、最小因子问题

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

案例：

输入

2

36

37

输出
9

37

2 python实现

def low_fac(n):k = nfor 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))