函数确定一个数是否为素数

  • 时间:
  • 分类: Python

你好,我做了一个函数来定义是否一个n是质数。但我有两个问题将被描述,但是首先让我们去功能:

选择 | 换行 | 行号
  1. def esprimo(n):
  2.     m=str(n)
  3.     if n<=1:
  4.         a=False
  5.     elif n==2:
  6.         a=True
  7.     elif int(m[-1])==(2 or 4 or 6 or 8 or 0 or 5):
  8.         a=False
  9.     elif n%3==0:
  10.         if n!=3:
  11.             a=False
  12.         else: a=True
  13.     elif n%7==0:
  14.         if n!=7:
  15.             a=False
  16.         else: a=True            
  17.     else:
  18.         a=True
  19.         check=11
  20.         while check<n+1:
  21.             if n%check==0:
  22.                 if n/check==1:
  23.                     pass
  24.                 else:
  25.                     a=False
  26.             check+=2

然而,它有两个问题:1. 当输入是8输出是正确的。这是唯一的错误,但是我不知道为什么。2. 优化不好,我想知道如果有事情我可以省略,或者一个更好的方法来定义一个数是否为素数谢谢你！

# 回答1

你的函数不返回任何东西。使用返回语句返回真正的如果n',假如果n不是质数。示例使用返回语句:

选择 | 换行 | 行号
  1. >>> def f(n):
  2. ...     if not n%2:
  3. ...         print "Number is divisible by 2"
  4. ...         return True
  5. ...     return False
  6. ... 
  7. >>> f(5)
  8. False
  9. >>> f(12)
  10. Number is divisible by 2
  11. True
  12. >>> 

一种有效的算法:如果n小于2,返回False如果n等于2,返回True如果不是n % 2,返回False开始一个for循环我的范围(从3开始,的平方根n增量2。如果不是n %我,返回False如果它被通过上面所有的,这是一个质数!

# 回答2

谢谢你,但是我忘记的一部分代码。最后它说:

选择 | 换行 | 行号
  1. return a
# 回答3

我也证明了你的算法及其速度方程是t = 1, 0 * 10 ^ -84 x ^ 51岁,我4和t = 7, 8 * 10 ^ -26 x ^ 16日,23日,所以我的速度更快。
# 回答4

对你有好处冈萨洛。太坏的结果不正确。我修改了你的代码有点:

选择 | 换行 | 行号
  1. def is_prime2(n):
  2.     if n<=1:
  3.         return False
  4.     elif n in (2, 3, 5, 7):
  5.         return True
  6.     elif str(n)[-1] in ('0', '2', '4', '5', '6', '8'):
  7.         return False
  8.     elif n%3==0:
  9.         return False
  10.     elif n%7==0:
  11.         return False
  12.     else:
  13.         for i in range(11, int(n**0.5)+1, 2):
  14.             if not n%i:
  15.                 return False
  16.     return True

我对比了三个函数使用的速度时间模块。is_prime()是我最初的建议,is_prime1()是你的原始代码,和is_prime2()代码修改。

选择 | 换行 | 行号
  1. if __name__ == '__main__':
  2.     import timeit
  3.     t = timeit.Timer("is_prime(2000097)", "from __main__ import is_prime")
  4.     print t.timeit()
  5.     t = timeit.Timer("is_prime1(2000097)", "from __main__ import is_prime1")
  6.     print t.timeit()
  7.     t = timeit.Timer("is_prime2(2000097)", "from __main__ import is_prime2")
  8.     print t.timeit()

使用2000097这个数字,结果几乎相同:

选择 | 换行 | 行号
  1. >>> 1.45488211364
  2. 1.42580345757
  3. 1.42388930047
  4. >>> 1.4366972181
  5. 1.44870719986
  6. 1.42893746692
  7. >>> 1.43660163505
  8. 1.43026986126
  9. 1.46972456191
  10. >>> 1.44520062355
  11. 1.4405034696
  12. 1.42799974136
  13. >>> 1.4306084289
  14. 1.44109168939
  15. 1.42320573522
  16. >>> 

使用2000095这个数字,你的原始代码失败。使用10次迭代代替1000000:

选择 | 换行 | 行号
  1. >>> 2.48837116033e-005
  2. 1.38539355502
  3. 1.83635415283e-005
  4. >>> 

你的原始代码的问题是,你查看最后一个数字是什么号码。而不是:elif int (m[1]) = =(2或4或6或8 0 5):应该是这样的:elif str (n) [1] (' 0 ', ' 2 ', ' 4 ', ' 5 ', ' 6 ', ' 8 '):

# 回答5

ooooooohh非常感谢你,我欠你一个人情,代码是一块金子。谢谢你！

标签: python

添加新评论