尝试创建一个包含 N 个第一个素数的数组

Question

我是编程新手，我正在尝试创建一种方法，returns 一个包含 N 个第一个素数的数组。我知道 ruby 中有一个质数 class，但我需要创建一个没有它的方法。

这是我到目前为止得到的结果，但我不断得到奇怪的结果。我觉得有一个简单的逻辑问题，但我找不到它（我不知道 ruby 中的 break 是如何工作的）。

备注：

我将我的第一次迭代限制在 2000 次以运行测试更快。
@num 是我必须放入 array_prime
中的质数个数

我输入 2，因为它是唯一的偶数素数，所以我可以在第二个循环中执行第 2 步

def find_prime_array
  array_prime = [2]
  while array_prime.size <= @num
    isPrime = true
    (1..2000).each do |i|
      (3..(i-1)).step(2) do |j| 
        if i % j == 0
          isPrime = false
          break
        end
      end
      array_prime << i if isPrime
    end
  end
  array_prime
end

在此先感谢您的帮助。

Answer 1

这是我的尝试（我不知道 ruby...）：

def find_prime_array
  array_prime = [2]
  candidate = 3
  while array_prime.size <= @num
    isPrime = true
    index = 0
    while index<array_prime.size AND array_prime[index] <= squareRoot(candidate) AND isPrime
      if candidate % array_prime[index] == 0
        isPrime = false
        break
      end
      index += 1
    end
    array_prime << candidate if isPrime
    candidate += 2
  end
  array_prime
end

想法是检查候选人是否可以被找到的素数整除，检查大于其平方根的除数是多余的。
递增 2 做得很好，因为递增 1 会浪费时间！

Answer 2

看起来您正在尝试实施 Sieve of Eratosthenes，修改为 return 一定数量的素数，而不是检查一定数量的候选项，但是您的方法存在几个问题。

您从 2 作为质数开始，但从 1 开始搜索。您将再次得到 1 和 2。您的搜索应该从 3 开始。

你说得对，你可以通过一次迭代两个来提高效率，但你已经从筛子中遗漏了 2 个，所以偶数仍然存在。您的候选人和您的除数都只需要是赔率。

您检查是否匹配了足够多的素数是在最外层循环中，因此它永远不会停止内层循环。

@num 应作为参数传入。

清理所有内容，并将内循环提取为函数以简化事情...

# Pass in the number of primes to make the function more useful. Default to @num.
def find_prime_array(num_primes = @num)
  # Start with 2 so we only have to check odd numbers.
  array_prime = [2]

  # Step through only the odd numbers.
  (3..2001).step(2) do |i|
    # Extract the prime check into a function.
    array_prime << i if prime?(i)

    # Stop when we have enough primes.
    break if array_prime.size >= num_primes
  end

  array_prime
end

def prime?(i)
  # Also only divide by only the odd numbers.
  (3..(i-1)).step(2) do |j| 
    return false if i % j == 0
  end
  
  return true
end

但我们可以更有效地做到这一点。筛子的强大之处在于您不必将每个候选人都除以每个奇数。您只需要除以目前找到的素数即可。

def find_prime_array(num_primes = @num)
  array_prime = [2]

  (3..2001).step(2) do |i|
    array_prime << i if prime?(i, array_prime)

    break if array_prime.size >= num_primes
  end

  array_prime
end

def prime?(i, array_prime)
  array_prime.each do |j| 
    return false if i % j == 0
  end
  
  return true
end

最后，我们可以更地道地做同样的事情，没有人为限制。

def find_prime_array(num_primes)
  primes = [2]

  (3..).step(2) do |candidate|
    if primes.none? { |prime| candidate % prime == 0 }
      primes << candidate
    end
    break if primes.size >= num_primes
  end

  return primes
end

尝试创建一个包含 N 个第一个素数的数组

Trying to create an array with N first primes numbers

ruby

arrays

primes

break