jd156166151616 2023-04-16 12:57 采纳率: 100%
浏览 87
已结题

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

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")
  • 写回答

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

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 4月17日
  • 已采纳回答 4月16日
  • 创建了问题 4月16日