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")

pta判断素数运行超时,如何解决?(语言-python)
- 写回答
- 好问题 0 提建议
- 关注问题
- 邀请回答
-
3条回答 默认 最新
- 社区专家-Monster-XH 2023-04-16 13:05关注
基于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")
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 2无用