如何在给定的数目中优化最大素因子？

Question

约束

1<=T<=10

10<=N<=10^2

输入

2

10

17

输出

5

17

这是我的代码

n=int(input())
for f in range(n):
    b=[]
    a=int(input())
    for i in range(1,a+1):
        if i>1:
            for j in range(2,i):
                if (i%j)==0:
                    break
            else:
                if a%i==0:

                     b.append(i)
    print(max(b))

解释

10是{2,5}，所以回答5

17本身就是17。

Answer 1

在约束条件中，如果T表示最多有10个测试用例，而N表示给定数目的范围在10到100之间，

最优化的方法之一是在代码中创建一个初始化列表，并为每次读取的输入打印预先计算的答案。:)

answer = [0, 1, 2, 3, 2, 5, 3, 7, 2, 3,
      5, 11, 3, 13, 7, 5, 2, 17, 3, 19,
      5, 7, 11, 23, 3, 5, 13, 3, 7, 29,
      5, 31, 2, 11, 17, 7, 3, 37, 19, 13,
      5, 41, 7, 43, 11, 5, 23, 47, 3, 7,
      5, 17, 13, 53, 3, 11, 7, 19, 29, 59,
      5, 61, 31, 7, 2, 13, 11, 67, 17, 23,
      7, 71, 3, 73, 37, 5, 19, 11, 13, 79,
      5, 3, 41, 83, 7, 17, 43, 29, 11, 89,
      5, 13, 23, 31, 47, 19, 3, 97, 7, 11, 5]

Answer 2

创建一个在100下面的素数列表。

对每个“i”只从'a‘到'a/2-1’运行一个循环，检查'i‘是否完全分隔'a’，是否存在于‘素数’中。

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

n=int(input())
for f in range(n):
    a=int(input())
    for i in range(a,int(a/2-1),-1):
        if(a%i==0 and i in primes):
          print(i)
          break

如果不想手动创建素数列表，可以首先使用它通过for循环创建素数列表：

import math

def isPrime(n): 
      
    if (n <= 1): 
        return False
    
    #check from sqrt(n) to 2
    for i in range(int(math.sqrt(n)),1,-1): 
        if (n % i == 0): 
            return False
  
    return True

primes = []
for i in range(100):
  if(isPrime(i)):
    primes.append(i)

n=int(input())
for f in range(n):
    a=int(input())
    for i in range(a,int(a/2-1),-1):
        if(a%i==0 and i in primes):
          print(i)
          break