pta判断素数运行超时，如何解决？(语言-python)

Question

M = int(input())
flag=1
if M == 2:
    print("Yes")
elif M <= 0:
    print("No")
elif M == 1:
    print("No")
else:
    for i in range(2, M):
        if M % i == 0:
            flag=0
            break
    if flag==1:
        print("Yes")
    else:
        print("No")

Answer 1

基于Monster 组和GPT的调写：
剪枝优化：

import math

M = int(input())
flag = 1
if M == 2:
    print("Yes")
elif M <= 0 or M == 1:
    print("No")
else:
    for i in range(2, int(math.sqrt(M)) + 1):
        if M % i == 0:
            flag = 0
            break
    if flag == 1:
        print("Yes")
    else:
        print("No")

用质数筛选法的优化

import math

# 构建素数表
MAXN = 1000000
is_prime = [True] * (MAXN + 1)
is_prime[0], is_prime[1] = False, False
for i in range(2, int(math.sqrt(MAXN)) + 1):
    if is_prime[i]:
        for j in range(i * i, MAXN + 1, i):
            is_prime[j] = False

M = int(input())
if M < 2 or not is_prime[M]:
    print("No")
else:
    print("Yes")