문제
이 알고리즘의 루비 버전을 그물에서 긁지 않고 설명을 바탕으로 직접 만들고 싶었습니다. 여기. 그러나 나는 두 가지를 알아낼 수 없습니다
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
- 왜 배열 끝까지 반복하지 않습니까?
- 위의 링크의 설명에 따르면 루프는 배열의 마지막 요소의 제곱이 현재 프라임보다 큽니다.
배열의 길이를 수정하는 삭제 작업과 관련이 있다고 확신합니다. 예를 들어, 내 기능은 현재 n = 10을 입력 할 때 현재 2,3,5,7,9,10을 생성합니다. 내가 이것을 어떻게 변화시킬 수 있는지에 대한 제안이 예상처럼 작동하게 만들 수 있습니까?
해결책
다음은 작동하는 것 같습니다. 나는 플로팅 포인트 산술을 꺼내어 제곱 루팅 대신 제곱했습니다. 또한 삭제 루프를 "SELECT"호출로 교체했습니다.
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
에스)
이것은 매우 간단한 구현입니다 Wikipedia 기사 pseudocode, a 비트 어레이.
#!/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
이것은 관심있는 사람들을위한 참조입니다. 코드는 이 지역.
이 코드는 Eratosthenes의 체도 사용합니다.
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[$_.to_i]
end
그리고 여기 있습니다 다른 것.
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)
또는
x = []
Prime.each(123) do |p|
x << p
end
여기에 주입을 사용하는 방법이있을 수 있지만 오늘은 내 머리를 아프게합니다.
제휴하지 않습니다 StackOverflow