Сито Эратосфена в Рубине
-
04-07-2019 - |
Вопрос
Вместо того, чтобы удалять версию Ruby этого алгоритма из сети, я хотел создать свою собственную на основе его описания здесь . Однако я не могу понять две вещи
def primeSieve(n)
primes = Array.new
for i in 0..n-2
primes[i] = i+2
end
index = 0
while Math.sqrt(primes.last).ceil > primes[index]
(primes[index] ** 2).step(primes.length - 1, primes[index])
{|x| x % primes[index] == 0 ? primes.delete(x) : ""}
index += 1
end
primes
end
<Ол>
Я уверен, что это как-то связано с операцией удаления, изменяющей длину массива. Например, моя функция в настоящее время дает 2,3,5,7,9,10, когда я ввожу n = 10, что, очевидно, не правильно. Любые предложения о том, как я могу изменить это, чтобы он работал так, как он должен?
Решение
Кажется, следующее работает. Я вынул арифметику с плавающей запятой и возводил в квадрат вместо квадратного корня. Я также заменил цикл удаления на «выбрать» звоните.
while primes[index]**2 <= primes.last
prime = primes[index]
primes = primes.select { |x| x == prime || x%prime != 0 }
index += 1
end
Редактировать. Думаю, я понял, как вы пытаетесь это сделать. Кажется, что работает следующее, и оно больше соответствует вашему первоначальному подходу.
while Math.sqrt(primes.last).ceil >= primes[index]
(primes[index] * 2).step(primes.last, primes[index]) do
|x|
primes.delete(x)
end
index += 1
end
Другие советы
Более быстрая реализация доступна на www.scriptol.org :
def sieve_upto(top)
sieve = []
for i in 2 .. top
sieve[i] = i
end
for i in 2 .. Math.sqrt(top)
next unless sieve[i]
(i*i).step(top, i) do |j|
sieve[j] = nil
end
end
sieve.compact
end
Я думаю, что это может быть улучшено немного таким образом:
def better_sieve_upto(n)
s = (0..n).to_a
s[0] = s[1] = nil
s.each do |p|
next unless p
break if p * p > n
(p*p).step(n, p) { |m| s[m] = nil }
end
s.compact
end
... во многом из-за более быстрой инициализации массива, я думаю, но это маргинально. (Я добавил #compact
к обоим, чтобы исключить нежелательные nil
s)
Это довольно простая реализация псевдокода статьи Википедии с использованием битовый массив.
#!/usr/bin/env ruby -w
require 'rubygems'
require 'bitarray'
def eratosthenes(n)
a = BitArray.new(n+1)
(4..n).step(2) { |i|
a[i] = 1
}
(3..(Math.sqrt(n))).each { |i|
if(a[i] == 0)
((i*i)..n).step(2*i) { |j|
a[j] = 1
}
end
}
a
end
def primes(n)
primes = Array.new
eratosthenes(n).each_with_index { |isPrime, idx|
primes << idx if isPrime == 0
}
primes[2..-1]
end
Это ссылка для тех, кто заинтересован. Код взят с этого сайта . р>
В этом коде также используется сито Эратосфена.
n = 1000000
ns = (n**0.5).to_i + 1
is_prime = [false, false] + [true]*(n-1)
2.upto(ns) do |i|
next if !is_prime[i]
(i*i).step(n, i) do |j|
is_prime[j] = false
end
end
count = 0
list = (0..n).map do |i|
count += 1 if is_prime[i]
count
end
while gets
puts list[ Это ссылка для тех, кто заинтересован. Код взят с этого сайта . р>
В этом коде также используется сито Эратосфена.
def eratosthenes(n)
nums = [nil, nil, *2..n]
(2..Math.sqrt(n)).each do |i|
(i**2..n).step(i){|m| nums[m] = nil} if nums[i]
end
nums.compact
end
p eratosthenes(100)
А вот и еще один .
<*>.to_i]
end
А вот и еще один .
<*>или
x = []
Prime.each(123) do |p|
x << p
end
Здесь может быть способ использовать инъекцию, но начальная вещь сегодня ранит мою голову.