ruby - Eratosthenes 变体筛法

Question

我想做一个不利用明显数学技巧的筛子。我想暴力破解它。我的算法是基于以下概念构思的，即筛子会大量检查非素数，并仅返回运算结果来检查这些结果，而不是找出什么是素数。我认为一些 Carmichael Numbers 证明它对于非常大的东西是无效的。我可能是错的。我继续检查一个范围内的数字，并遵循 Wikipedia 给出的基本算法。 .

def primes(n)
  nums = (2..n)
  not_prime = []
  primes = []
  nums.to_a.each_with_index do |it, idx|
      primes << it unless not_prime.include?(it)
      p primes.last
      p nums.step(primes.last).to_a
      nums.step(primes.last).each_with_index do |num, idx|
        next if idx == 0
        not_prime << num
      end
  end

  primes
end

当我的范围达到这条线时:

nums.step(primes.last).each_with_index

对于除第一个 (2) 之外的数字，我得到一个 off-by-x 错误(我相信在列表中复合)。例如，所有非质数的二倍数都被找到，但是对于三的倍数，区间上的步长返回2, 5, 8、11 等，相差一个。

我正在尝试使用 Range 对象或转换为 Array 来找出解决方案，但我喜欢我的(错误)解决方案的简洁性。有人认为他们可以帮我解决这个问题吗？

编辑:

我修好了!解决方案是创建一个全新的范围来迭代而不是采用原始范围。见下文。向 Jörg W Mittag 大声疾呼，寻求灵感来创建一个新的范围，而不是试图摆弄我正在尝试做的原始不可变对象(immutable对象)。圆孔中的方钉有时听起来好多了。

def primes(n)
  nums = (2..n)
  not_prime = []
  primes = []
  nums.to_a.each_with_index do |it, idx|
      next if not_prime.include?(it)
      primes << it 
      ((primes.last)..n).step(primes.last).each_with_index do |num, idx|
        next if idx == 0 || num == primes.last
        not_prime << num
      end
  end

  primes
end

Answer 1

def primes(n)
  nums = (2..n)
  not_prime = []
  primes = []
  nums.to_a.each_with_index do |it, idx|
      next if not_prime.include?(it)
      primes << it 
      ((primes.last)..n).step(primes.last).each_with_index do |num, idx|
        next if idx == 0 || num == primes.last
        not_prime << num
      end
  end

  primes
end