isPrime Python语言函数

Question

所以我能够通过互联网的一些帮助来解决这个问题,这就是我得到的:

def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False

    return True

但我的问题是如何做到这一点,但为什么.我知道1不被认为是"素数",即使它是,并且我理解如果它在范围内除以ANYTHING则自动为素数,因此返回False语句.但我的问题是"n"在这里的平方是什么角色？非常感谢您的关注

Ps我非常缺乏经验,一个月前刚刚开始编程:S

Answer 1

在互联网上的许多素性测试中,考虑以下主要测试:

def is_prime(n):
  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(n**0.5)
  f = 5
  while f <= r:
    print '\t',f
    if n%f == 0: return False
    if n%(f+2) == 0: return False
    f +=6
  return True    

考虑素数5003:

print is_prime(5003)

打印:

 5
 11
 17
 23
 29
 35
 41
 47
 53
 59
 65
True

该行r = int(n**0.5)评估为70(5003的平方根为70.7318881411并int()截断此值)

由于前几个测试和循环中间的测试,循环只需要每隔6个数进行一次评估.

考虑下一个奇数(因为除了2之外的所有偶数都不是素数)5005,同样的东西打印:

 5
False

该限制是平方根,因为x*y == y*x该函数只需要进行1循环就可以找到5005可被5整除,因此不是素数.由于5 X 1001 == 1001 X 5(并且都是5005),我们不需要在循环中一直到1001来知道我们在5知道什么!

现在,让我们来看看你的算法:

def isPrime(n):
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False

    return True

有两个问题:

1. 它不测试是否n小于2,并且没有小于2的素数;
2. 它测试2和n**0.5之间的每个数字,包括所有偶数和所有奇数.由于每个可被2整除的大于2的数字不是素数,我们可以通过仅测试大于2的奇数来加速它.

所以:

def isPrime2(n):
    if n==2 or n==3: return True
    if n%2==0 or n<2: return False
    for i in range(3,int(n**0.5)+1,2):   # only odd numbers
        if n%i==0:
            return False    

    return True

好的 - 它加快了大约30%(我对它进行了基准测试......)

我使用的算法is_prime仍然快2倍,因为只有每6个整数循环通过循环.(再一次,我对它进行了基准测试.)

旁注:x**0.5是平方根:

>>> import math
>>> math.sqrt(100)==100**0.5
True

附注2:素性测试是计算机科学中一个有趣的问题.

Answer 2

有n**.5,你不是正方形,而是取平方根.

考虑数字20; 整数因子是1,2,4,5,10和20.当你将20除以2并得到10时,你知道它也可以被10整除,而不必检查.当你将它除以4并得到5时,你知道它可以被4和5整除,而不必检查5.

在达到这些因素的中间点后,您将没有更多数字来检查您之前尚未识别的因素.因此,您只需要中途看看是否有素数,并且可以通过取数字的平方根来找到这个中间点.

此外,原因1不是素数是因为素数被定义为具有2个因子,1和它们本身.即2是1*2,3是1*3,5是1*5.但是1(1*1)本身只有1个因子.因此,它不符合这个定义.

Answer 3

之前问过这个问题,但我有一个较短的解决方案

isPrime(Number):
    return 2 in [Number,2**Number%Number]

如果数字是素数,则数学运算将始终返回2,而不是2.但如果2是给定数字,则它将附加到我们正在查看的列表中.

2^5=32    32%5=2
2^7=128   128%7=2
2^11=2048 2048%11=2

等等 ...

如果Number为Prime,则isPrime()返回True,否则返回False.

Answer 4

下面没有进行浮点运算.这更快,并且可以容忍更高的论点.你必须只去平方根的原因是,如果一个数字的因子大于它的平方根,它也有一个小于它的因子.

def is_prime(n):
    """"pre-condition: n is a nonnegative integer
    post-condition: return True if n is prime and False otherwise."""
    if n < 2: 
         return False;
    if n % 2 == 0:             
         return n == 2  # return False
    k = 3
    while k*k <= n:
         if n % k == 0:
             return False
         k += 2
    return True

Answer 5

这种方法会比这里的递归和枚举方法慢，但使用威尔逊定理，并且只是一行：

from math import factorial

def is_prime(x):
    return factorial(x - 1)  % x == x - 1

Answer 6

求数字的平方根是为了提高效率。例如。如果我想找出 36 的因数，则可以与其自身相乘形成 36 的最大数字是 6。7*7 = 49。

因此，36 的每个因数都必须乘以 6 或更少的数。

Answer 7

def is_prime(x):
    if x < 2:
        return False
    elif x == 2:
        return True  
    for n in range(2, x):
        if x % n ==0:
            return False
    return True