Как создать первые n простых чисел?

Ответ 1

В 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, поэтому вы можете делать всевозможные забавные вещи, такие как фильтрация, сопоставление и т.д.

Ответ 2

require 'prime'

Prime.first(10) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Ответ 3

Если вы хотите сделать это самостоятельно, то что-то вроде этого может работать:

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

Ответ 4

Люди уже упоминали класс 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 }

Ответ 5

Отъезд Сито Эратосфена. Это не относится к Ruby, но это алгоритм для генерации простых чисел. Идея этого алгоритма заключается в том, что у вас есть список/массив чисел, которые говорят

2..1000

Вы получите первое число, 2. Перейдите в список и устраните все, что делится на 2. Вы останетесь со всем, что не делится на 2, кроме 2 (например, [2,3,5,7, 9,11... 999]

Перейдите к следующему номеру, 3. И снова устраните все, что вы можете разделить на 3. Продолжайте, пока не достигнете последнего номера, и вы получите массив простых чисел. Надеюсь, что это поможет.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Ответ 6

# 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

Ответ 7

Реализовано сито эратосфена (более или менее)

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 простые числа, но я думаю, что адаптация не потребует больших усилий.

Ответ 8

Вот способ генерации простых чисел до аргумента "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

Ответ 9

Я думаю, что это может быть дорогостоящим решением для очень больших максимальных чисел, но, похоже, работает в противном случае:

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

Ответ 10

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.

Не прибегая к усилиям по внедрению алгоритма решета, время можно быстро сохранить, только проверив делимость до квадратного корня и пропустив нечетные числа. Затем, итерации по номерам, проверка на грубость.

Помните: машинное время человеческое время >

Ответ 11

Я сделал это для кодирования ката и использовал Сито Эратосфена.

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)

Ответ 12

Ruby: печать N простых чисел 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

Ответ 13

Совсем не связан с самим вопросом, но FYI:

• если кто-то не хочет продолжать генерировать простые числа снова и снова (a.k.a. жадный ресурс)
• или, может быть, вы уже знаете, что вы должны каким-то образом работать с последующими простыми цифрами.
• другие неизвестные и замечательные случаи

Попробуйте этот фрагмент:

  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. Дополнительная информация

Ответ 14

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)