如何在Python中编写高效的代码来查找素数? 我已经尝试了简单的代码,我需要更有效的代码。 例如: num = int(input('输入数字以检查是否为质数:')) for i in range(2,num):如果num % i == 0:print("Not Prime")break else:print("素数")
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
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
2条答案
按热度按时间yrefmtwq1#
要回答你的问题,这里有一种方法,它将确定一个数字是否是素数比你写的更有效,尽管对于大数,它仍然不是最好的。此外,该解决方案解决了用户输入0、1或2的情况。
hpxqektj2#
我发现Itprorh66的答案很难用
r
和f
变量来阅读。Jaosnharper关于只循环到平方根的评论是一个好主意。下面是一些代码,可以让这个过程更快: