如何生成前n个素数？
我正在学习Ruby并做一些数学的东西。 我想做的其中一件事是生成素数。
我想生成前十个素数和前十个素数。 我测试一个数字是否有素数是没有问题的，但是想知道生成这些数字的最佳方法是什么？
我使用以下方法来确定数字是否为素数：
class Integer < Numeric def is_prime? return false if self <= 1 2.upto(Math.sqrt(self).to_i) do |x| return false if self%x == 0 end true end end 在Ruby 1.9中，有一个Prime类可用于生成素数，或者测试数字是否为素数：
require 'prime' Prime.take(10) #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] Prime.take_while {|p| p < 10 } #=> [2, 3, 5, 7] Prime.prime?(19) #=> true
Prime实现了each方法并包含Enumerable模块，因此您可以执行各种有趣的操作，如过滤，映射等。
require 'prime' Prime.first(10) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
如果你想自己做，那么像这样的东西可以工作：
class Integer < Numeric def is_prime? return false if self <= 1 2.upto(Math.sqrt(self).to_i) do |x| return false if self%x == 0 end true end def next_prime n = self+1 n = n + 1 until n.is_prime? n end end
现在获得前10个素数：
e = Enumerator.new do |y| n = 2 loop do y << n n = n.next_prime end end primes = e.take 10
人们已经提到过Prime课程，这绝对是最佳选择。 有人还向您展示了如何使用Enumerator ，我想使用Fiber贡献一个版本（它使用您的Integer#is_prime?方法）：
primes = Fiber.new do Fiber.yield 2 value = 3 loop do Fiber.yield value if value.is_prime? value += 2 end end 10.times { p primes.resume }
看看Eratosthenes的Sieve。 这不是特定于Ruby的，但它是一种生成素数的算法。 这个算法背后的想法是你有一个列表/数组说
2..1000
你抓住第一个数字，2。浏览列表并删除所有可被2整除的东西。你将留下除2之外不能被2整除的所有东西（例如[2,3,5,7,9， 11 … 999]
转到下一个数字，3。再次，消除你可以除以的所有东西。继续前进，直到你到达最后一个数字，你将得到一个素数数组。 希望有所帮助。
# First 10 Prime Numbers number = 2 count = 1 while count < 10 j = 2 while j <= number break if number%j == 0 j += 1 end if j == number puts number count += 1 end number += 1 end
实施Eratosthene筛选（或多或少）
def primes(size) arr=(0..size).to_a arr[0]=nil arr[1]=nil max=size (size/2+1).times do |n| if(arr[n]!=nil) then cnt=2*n while cnt <= max do arr[cnt]=nil cnt+=n end end end arr.compact! end
此外，这是一个我喜欢很多的单线程
def primes_c a p=[];(2..a).each{|n| p.any?{|l|n%l==0}?nil:p.push(n)};p end
当然那些会在前n数字中找到素数，而不是前n素数，但我认为改编不需要太多努力。
这是一种从头开始生成素数到“max”参数的方法，无需使用Prime或Math。 让我知道你的想法。
def prime_test max primes = [] (1..max).each {|num| if (2..num-1).all? {|denom| num%denom >0} then primes.push(num) end } puts primes end prime_test #enter max
我认为这可能是一个非常大的最大数字的昂贵的解决方案，但似乎工作得很好：
def multiples array target = array.shift array.map{|item| item if target % item == 0}.compact end def prime? number reversed_range_array = *(2..number).reverse_each multiples_of_number = multiples(reversed_range_array) multiples_of_number.size == 0 ? true : false end def primes_in_range max_number range_array = *(2..max_number) range_array.map{|number| number if prime?(number)}.compact end
class Numeric def prime? return self == 2 if self % 2 == 0 (3..Math.sqrt(self)).step(2) do |x| return false if self % x == 0 end true end end
有了这个，现在3.prime? 返回true ，和6.prime? 返回false 。
在没有努力实施筛分算法的情况下，通过仅validation可分性直到平方根并跳过奇数，仍然可以快速节省时间。 然后，遍历数字，检查完整性。
记住： 人类时间>机器时间。
我为编码kata做了这个，并使用了Eratosthenes的Sieve。
puts "Up to which number should I look for prime numbers?" number = $stdin.gets.chomp n = number.to_i array = (1..n).to_a i = 0 while array[i]**2 < n i = i + 1 array = array.select do |element| element % array[i] != 0 || element / array[i] == 1 end end puts array.drop(1)
Ruby：打印N prime Numbers http://mishra-vishal.blogspot.in/2013/07/include-math-def-printnprimenumbernoofp.html
include Math def print_n_prime_number(no_of_primes=nil) no_of_primes = 100 if no_of_primes.nil? puts "1 \n2" count = 1 number = 3 while count < no_of_primes sq_rt_of_num = Math.sqrt(number) number_divisible_by = 2 while number_divisible_by <= sq_rt_of_num break if(number % number_divisible_by == 0) number_divisible_by = number_divisible_by + 1 end if number_divisible_by > sq_rt_of_num puts number count = count+1 end number = number + 2 end end print_n_prime_number
与问题本身完全无关，但仅供参考：
- 如果有人不想一次又一次地生成素数（又名贪婪的资源保护者）
- 或者你可能已经知道你必须以某种方式使用后续的素数
- 其他未知和奇妙的案件
尝试使用此代码段：
require 'prime' for p in Prime::Generator23.new # `p` brings subsequent prime numbers until the end of the days (or until your computer explodes) # so here put your fabulous code break if #.. I don't know, I suppose in some moment it should stop the loop end fp
如果需要，还可以使用另一个更复杂的生成器作为Prime::TrialDivisionGenerator或Prime::EratosthenesGenerator 。 更多信息
def get_prime(number) (2..number).each do |no| if (2..no-1).all? {|num| no % num > 0} puts no end end end get_prime(100)