ruby 1.8 prime succ算法

发布时间：2020-12-17 02:37:41 所属栏目：百科来源：网络整理

导读：我搜索了我能想象到的每个站点,并且无法确定 ruby 1.8用于在mathn下的Prime类中创建素数列表的基本算法.以下是succ方法的可运行版本,称为100次(为了找到第100个素数).有谁知道这是如何工作的？ number_of_primes = 100seed = 1primes = Array.newcounts = Ar

我搜索了我能想象到的每个站点,并且无法确定 ruby 1.8用于在mathn下的Prime类中创建素数列表的基本算法.以下是succ方法的可运行版本,称为100次(为了找到第100个素数).有谁知道这是如何工作的？

number_of_primes = 100

seed = 1
primes = Array.new
counts = Array.new


while primes.size < number_of_primes
  i = -1
  size = primes.size
  while i < size
    if i == -1
      seed += 1
      i += 1
    else
      while seed > counts[i]
        counts[i] += primes[i]
      end
      if seed != counts[i]
        i += 1
      else
        i = -1
      end
    end
  end
  primes.push seed
  counts.push (seed + seed)
end

puts seed

实际代码当然是：http://ruby-doc.org/stdlib-1.8.7/libdoc/mathn/rdoc/Prime.html

它看起来不像筛选算法,因为没有预定义的列表可以筛选,它不是试验分割算法,因为没有除法或模数运算.我完全难过了.

解决方法

该算法基于Eratosthenes的筛子.

种子是正在测试的完整性的整数. primes是小于seed的primes列表,count包含大于seed的相应最小倍数.

将计数视为“下一个”划掉数字的列表,但每个素数只有一个,不断更新.当找到下一个最大倍数时,如果我们得到完全种子,那么它不是素数,因此它重置外环(i = -1).

只有当我们更新了更多倍数的列表而没有遇到确切的种子时,才能推断出种子是素数.

这里的代码略有简化并注释：

number_of_primes = 100

seed = 1
primes = []
counts = []

while primes.size < number_of_primes
  seed += 1
  i = 0
  while i < primes.size      # For each known prime
    while seed > counts[i]   # Update counts to hold the next multiple >= seed
      counts[i] += primes[i] # by adding the current prime enough times
    end
    if seed != counts[i]
      i += 1    # Go update next prime
    else
      i = 0     # seed is a multiple,so start over...
      seed += 1 # with the next integer
    end
  end
  # The current seed is not a multiple of any of the previously found primes,so...
  primes.push seed
  counts.push (seed + seed)
end

puts seed

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!