改进代码以查找素数 [英] Improve code to find prime numbers
本文介绍了改进代码以查找素数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我大约三天前写了这个python代码,我卡在这里,我认为它可以更好,但我不知道如何改进它.你们能帮我吗?
I wrote this python code about 3 days ago, and I am stuck here, I think it could be better, but I don't know how to improve it. Can you guys please help me?
# Function
def is_prime(n):
if n == 2 or n == 3:
return True
for d in range(3, int(n**0.5), 2):
if n % d == 0:
return False
return True
推荐答案
找到相对较小质数的一个好的确定性方法是使用 筛分.
A good deterministic way to find relatively small prime numbers is to use a sieve.
此技术背后的数学原理如下:要检查一个数是否为素数,只需检查它是否不能被其他素数整除即可.
The mathematical principle behind this technique is the following: to check if a number is prime, it is sufficient to check that it is not divisible by other primes.
import math
def is_prime(n):
# Prepare our Sieve, for readability we make index match the number by adding 0 and 1
primes = [False] * 2 + [True] * (n - 1)
# Remove non-primes
for x in range(2, int(math.sqrt(n) + 1)):
if primes[x]:
primes[2*x::x] = [False] * (n // x - 1)
return primes[n]
# Or use the following to return all primes:
# return {x for x, is_prime in enumerate(primes) if is_prime}
print(is_prime(13)) # True
为了可重用性,您可以修改上述代码以返回 n
以内的所有质数的 set
.
For reusability your could adapt the above code to return the set
of all prime numbers up to n
.
这篇关于改进代码以查找素数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文