私はRubyを学んでいて、いくつかの数学をやっています。私がやりたいことの 1 つは、素数を生成することです。
最初の 10 個の素数と最初の 10 個のみを生成したい。数値をテストして素数かどうかを確認するのに問題はありませんが、これらの数値を生成する最良の方法は何ですか?
次の方法を使用して、数値が素数かどうかを判断しています。
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 モジュールが含まれているため、フィルタリングやマッピングなど、あらゆる種類の楽しいことを実行できます。
自分でやりたい場合は、次のようなことができます。
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
require 'prime'
Prime.first(10) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
エラトステネスの篩を見てください。これは Ruby 固有のものではありませんが、素数を生成するためのアルゴリズムです。このアルゴリズムの背後にある考え方は、数字のリスト/配列があるということです
2..1000
最初の数 2 を取得します。リストを調べて、2 で割り切れるものをすべて削除します。2 自体以外の 2 で割り切れないものはすべて残ります (例: [2,3,5,7,9, 11...999]
次の数 3 に進みます。また、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
これは非常に大きな最大数の場合は高価なソリューションになる可能性があると思いますが、それ以外の場合はうまく機能するようです:
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
エラトステネのふるいを実装しました（多かれ少なかれ）
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が、適応にはそれほど努力は必要ないと思います.
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。
ふるいアルゴリズムを実装する努力をしなくても、平方根まで割り切れるかどうかを検証し、奇数をスキップするだけで、時間を大幅に節約できます。次に、数値を反復処理して、素数をチェックします。
覚えておいてください：人間の時間>機械の時間。
私はコーディングのカタのためにこれを行い、エラトステネスのふるいを使用しました.
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)
質問自体とはまったく関係ありませんが、参考までに：
このスニペットを試してください：
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::TrialDivisionGeneratororとして使用することもできますPrime::EratosthenesGenerator。より詳しい情報
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
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)