我在python编程中遇到了一个素数查询问题

idfiyjo8  于 2023-06-25  发布在  Python
关注(0)|答案(2)|浏览(99)

如何在Python中编写高效的代码来查找素数?
我已经尝试了简单的代码,我需要更有效的代码。
例如:
num = int(input('输入数字以检查是否为质数:'))
for i in range(2,num):如果num % i == 0:print("Not Prime")break
else:print("素数")

yrefmtwq

yrefmtwq1#

要回答你的问题,这里有一种方法,它将确定一个数字是否是素数比你写的更有效,尽管对于大数,它仍然不是最好的。此外,该解决方案解决了用户输入0、1或2的情况。

def is_prime(n):
    """
    Integer -> Boolean
    returns True if n is a prime number
    """
    if n == 2 or n == 3:
        return True
    if n < 2 or n % 2 == 0:
        return False
    if n < 9:
        return True
    if n % 3 == 0:
        return False

    r = int(sqrt(n))
    f = 5
    while f <= r:
        if n % f == 0:
            return False
        if n % (f + 2) == 0:
            return False
        f += 6
    return True
hpxqektj

hpxqektj2#

我发现Itprorh66的答案很难用rf变量来阅读。Jaosnharper关于只循环到平方根的评论是一个好主意。下面是一些代码,可以让这个过程更快:

import math

def is_prime(number: int) -> bool:
    """
    Summary:
        Check if an integer is a prime number.

    Returns:
        bool: If the input (number) is a prime number or not.
    """

    # One, zero, and negative numbers do not follow the definition of a prime
    # number.
    if number < 2:
        return False

    # Two is an exception with even numbers when considering whether they are
    # prime or not, so it is handled here.
    if number == 2:
        return True

    # Even numbers are always composite (except for two).
    if number % 2 == 0:
        return False

    # Plus one is used to include the final number while in the for-loop.
    square_root_number = math.isqrt(number) + 1

    # There is an increase of two instead of one to iterate over odd divisors
    # only.
    # The for-loop starts at three because numbers lower than three
    # have already been handled.
    for divisor in range(3, square_root_number, 2):
        if number % divisor == 0:
            return False

    return True

相关问题