3

我似乎无法使用此代码生成随机素数，有人可以帮助我吗？

def RandomPrime():
  prime = False
  while prime == False:
    n = random.randint(10000, 100000)
    if n % 2 != 0:
      for x in range(3, int(n**0.5), 2):
        if n % x ==0:
          prime = False
        else:
          prime = True


  return n
4

4 回答 4

4

想象一下如果最后一个数字range(3, int(n**0.5), 2)不是 的整数除数会发生什么n：

if n % x ==0:
    prime = False # not this
else:
    prime = True # this

因此，即使所有先前的检查都已评估False，您也可以称其n为素数。解决此问题的代码的最小更改是：

prime = prime and True # or 'prime &= True'

因此，如果prime已经存在 False，它仍然存在False。

但是，请记住，对于素数，如果这些检查中的任何False n一个不是素数。您可以使用 this 和 Python 的andand all（懒惰地评估，即一旦找到 a 就不要继续检查False）来更有效地实现：

def rand_prime():
    while True:
        p = randint(10000, 100000)
        if (r % 2 != 0 and
            all(p % n != 0 for n in range(3, int(((p ** 0.5) + 1), 2))):
            return p

为了获得更好的性能，请注意它randrange包含一个step参数，就像range，所以您可以跳过所有偶数（绝对不是素数！）：

def rand_prime():
    while True:
        p = randrange(10001, 100000, 2)
        if all(p % n != 0 for n in range(3, int((p ** 0.5) + 1), 2)):
            return p

注意：在我看来， sqrt(n)（来自math）对于其他技术含量较低的读者来说比n ** 0.5（尽管它可能更有效也可能不是更有效）更清楚一些。

于 2014-01-10T12:05:12.703 回答
0

看一下标签： else 应该指整个 for 循环，而不是 iF

def RandomPrime():
  prime = False
  while prime == False:
    n = random.randint(10000, 100000)
    if n % 2 != 0:
      for x in range(3, int(n**0.5), 2):
        if n % x ==0:
          break
      else:
          prime = True


  return n
于 2014-01-10T11:29:22.453 回答
0

There're errors in your code:

  1. Incorrect "else:"; you can't declare number being prime if a remainder is not 0; All the remaiders should be non-zeros
  2. int(n*0.5) should be int(n*0.5 + 1) to prevent round-up errors

The possible solution is

def RandomPrime():
  while True:
    n = random.randint(10000, 100000)

    if n % 2 == 0:
      continue;

    prime = True;

    for x in range(3, int(n**0.5 + 1), 2):
      if n % x == 0:
        prime = False;

        break; 

    if prime: 
      return n
于 2014-01-10T11:30:05.040 回答
0

正确的逻辑，您正在设置True时n % x！=0第一次：

  for x in range(3, int(n**0.5), 2):
    if n % x ==0:
      prime = False
    else:
      prime = True

应该：

  prime = False
  for x in range(3, int(n**0.5), 2):
    if n % x ==0:
      break
  else: 
    prime = True

阅读break 和 continue 语句，以及循环上的 else 子句。

编写等效代码的较短方法是（来自@ Steve Jesso）：

prime = all(n % x != 0 for x in range(3, int(n**0.5), 2)
于 2014-01-10T11:25:54.307 回答