web-gelistirme-sc.com

İlk n asal sayıları nasıl oluştururum?

Ruby'yi öğreniyorum ve bazı matematik işleri yapıyorum. Yapmak istediğim şeylerden biri asal sayılar üretmektir.

İlk on asal sayıyı ve sadece ilk onu oluşturmak istiyorum. Asal sayı olup olmadığını anlamak için bir sayıyı test etmekte hiçbir sorunum yok, ancak bu sayıları üretmenin en iyi yolunun ne olduğunu merak ediyor muydum?

Sayının asal olup olmadığını belirlemek için aşağıdaki yöntemi kullanıyorum:

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
24
Tony Petley

Ruby 1.9'da, asal sayılar oluşturmak için veya bir sayının asal olup olmadığını sınamak için kullanabileceğiniz bir Prime sınıfı vardır:

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 yöntemini uygular ve Numaralandırılabilir modülünü içerir, böylece filtreleme, haritalama vb. Her türlü eğlenceli şeyi yapabilirsiniz.

45
Scott Olson
require 'prime'

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

Kendin yapmak istersen, böyle bir şey işe yarayabilir:

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

Şimdi ilk 10 astarı alalım:

e = Enumerator.new do |y|
    n = 2
    loop do
        y << n
        n = n.next_prime
    end
end

primes = e.take 10
10
z5h

İnsanlar daha önce Prime sınıfından bahsetti; Birisi size Enumerator 'un nasıl kullanılacağını da gösterdi ve Fiber kullanarak bir versiyona katkıda bulunmak istedim (Integer#is_prime? metodunu kullanıyor):

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 }
7
Michael Kohl

Eratosthenes Elek göz atın. Bu Ruby'ye özgü değildir, ancak asal sayılar üreten bir algoritmadır. Bu algoritmanın arkasındaki fikir, şöyle bir liste/numara diziniz olmasıdır.

2..1000

İlk sayıyı aldınız, 2. Listeyi gözden geçirin ve bölünebilir olan her şeyi elimine alın. 2 tarafından bölünmeyen her şeyden 2 kişi kalacaksınız (ör. [2,3,5,7,9, 11 ... 999]

Bir sonraki sayıya gidin, 3. Ve yine bölebileceğiniz her şeyi ortadan kaldırın 3. Son sayıya ulaşana kadar devam edin ve bir asal sayı dizisi elde edin. Umarım yardımcı olur.

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

7
denniss
# 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
3
Jyothu

Bunu kodlayan bir kata için yaptım ve Eratosthenes Eleklerini kullandım.

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)
1
Max Durden
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

Bununla, şimdi 3.prime?true değerini ve 6.prime?false değerini döndürür. 

Elek algoritmasını uygulama çabalarına girmeden, zaman zaman sadece kök kökene kadar bölünebilirliği doğrulamak ve tek sayıları atlamak suretiyle hızlı bir şekilde tasarruf edilebilir. Ardından, önceliği kontrol ederek sayıları tekrarlayın.

Unutmayın: insan zamanı> makine zamanı.

1
Rishi

Bunun çok büyük maksimum sayılar için pahalı bir çözüm olabileceğini düşünüyorum ancak başka türlü de iyi sonuç veriyor:

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
1
Shay Narang

Asal sayıları Prime veya Math kullanmadan sıfırdan "max" argümanına kadar üretmenin bir yolu. Ne düşündüğü söyle.

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
1
Sam S

Eratosten Elek Uygulandı (az çok)

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

Üstelik işte çok sevdiğim tek gömlek

def primes_c a
    p=[];(2..a).each{|n| p.any?{|l|n%l==0}?nil:p.Push(n)};p
end

Elbette bunlar ilk n sayılarında primleri bulacaktır, ilk n astarlarını değil, bir uyarlamanın fazla çaba gerektirmeyeceğini düşünüyorum.

1
Gabber

Sorunun kendisiyle hiç ilişkili değil, ancak Bilginize:

  • birisi tekrar tekrar asal sayılar oluşturmaya devam etmek istemiyorsa (a.k.a. açgözlü kaynak koruyucusu)
  • veya belki de zaten bir şekilde sonraki asal sayılarla çalışmak zorunda olduğunuzu biliyorsunuzdur.
  • diğer bilinmeyen ve harika davalar

Bu pasajı dene:

  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

İhtiyacınız olursa, başka bir daha karmaşık jeneratörleri Prime::TrialDivisionGenerator veya Prime::EratosthenesGenerator olarak da kullanabilirsiniz. Daha fazla bilgi

0
Alter Lagos

Ruby: N asal sayılarını yazdırı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
0
user2206324