require 'benchmark' def eratosthenes(to_n) list = (2..to_n).to_a list.each do n (n..to_n).each {x list.delete(x) if x % n == 0 and x != n } end return list end thousand_sieve = eratosthenes(1000) benchmark = Benchmark.realtime do 1.upto(1000) do n puts "#{n} is prime." if thousand_sieve.include? n end end puts "Time = %.5f seconds." %benchmark
22 Replies  17567 Views  Last Post: 14 December 2011  06:40 AM
#16
Re: Ruby Challenge: Prime Numbers
Posted 01 July 2011  11:01 AM
#17
Re: Ruby Challenge: Prime Numbers
Posted 31 October 2011  04:10 PM
The solution contains an unnecessary puts statement showing the number of iterations for comparison.
It is based on two precepts:
#1) Start with 2 and look for factors of N. Return false if you find any.
#2) Each time you increase your iterator by 1, reduce the comparison value to the maximum possible integer you could reach. (i.e. if your looking for factors of 127 and you start off with 2, then when 2 iterates to 3, you're not going to have to go past 42 (127/3), since doing so would imply a number less than 3 is a factor.)
I have included some iteration counts for certain integers compared to running through all the numbers between 1 and the original value divided by 2. Also, I know I don't need "return" in front of true, but I was being consistent since I do need it to break from the while loop properly.
class Integer def isprime? i = 2 j = self while (i < j) do (self % i == 0) && (return false) i += 1 j = self / i end puts "Iterations: #{i2}" return true end end Examples: PrimeNumber ((N/2)1) isprime? Completion 17 7 2 ~0.004s 47 22 5 ~0.008s 97 47 8 ~0.008s 311 154 16 ~0.008s 3,779 1,888 59 ~0.008s 10,093 5,045 98 ~0.010s 115,249 57,623 337 ~0.011s 939,391 469,694 967 ~0.012s 433,494,437 216,747,217 20,819 ~0.019s 29,741,215,073 14,870,607,535 172,454 ~0.177s 10,000,000,000,129 5,000,000,000,063 3,162,276 ~2.906s 99,194,853,094,755,497 49,597,426,547,377,747 314,952,142 ~5m10.285s
That last one is probably unacceptable, but you really have to get into the quadrillions before this algorithm starts to slow down.
Anyway, that my two cents.
Thanks,
jace427
#18
Re: Ruby Challenge: Prime Numbers
Posted 31 October 2011  04:57 PM
class Integer def isprime? (self < 2) && (return false) i = 2 j = self while (i < j) do (self % i == 0) && (return false) i += 1 j = self / i end puts "Iterations: #{i2}" return true end end
#19
Re: Ruby Challenge: Prime Numbers
Posted 01 November 2011  02:32 PM
To be more pedantic still: a distinction should be made between deterministic and probabilistic tests for primality. The fastest deterministic algorithm  that I am aware of  simply divides the number by all of the primes <= the square root of the number being tested; if a prime factor is found the number is nonprime. This algorithm however requires an array of precomputed primes making it unsuitable for applications such as RSA, which utilise massive primes.
Just my £0.02
#20
Re: Ruby Challenge: Prime Numbers
Posted 01 November 2011  02:51 PM
RetardedGenius, on 01 November 2011  02:32 PM, said:
To be more pedantic still: a distinction should be made between deterministic and probabilistic tests for primality. The fastest deterministic algorithm  that I am aware of  simply divides the number by all of the primes <= the square root of the number being tested; if a prime factor is found the number is nonprime. This algorithm however requires an array of precomputed primes making it unsuitable for applications such as RSA, which utilise massive primes.
Just my £0.02
Agreed, and perhaps I wasn't clear about my comparison choices. Knowing nonprimes would not be a valid citeria for comparison based on the fact that this algorithm will short circuit at the first factor it finds, I chose all known primes. This was intentional to make it a fair comparison. To your second point, I only chose a deterministic approach, as it was a sure thing, so that was also intentional. A probabilistic approach might make more sense for massive primes. Thank you for your observations.
jace427
P.S. ..and please excuse my cultural insensitivity. I should have used 0.02 monetary units instead of cents.
#21
Re: Ruby Challenge: Prime Numbers
Posted 28 November 2011  11:28 AM
RetardedGenius, on 01 November 2011  02:32 PM, said:
To be more pedantic still: a distinction should be made between deterministic and probabilistic tests for primality. The fastest deterministic algorithm  that I am aware of  simply divides the number by all of the primes <= the square root of the number being tested; if a prime factor is found the number is nonprime. This algorithm however requires an array of precomputed primes making it unsuitable for applications such as RSA, which utilise massive primes.
Just my £0.02
No there are far better deterministic tests for primality, read http://en.wikipedia....rministic_tests . I'd be very interested if anyone would have a go at one.
Also any deterministic test can be combined with a probabilistic test as in only do the deterministic test if the probabilistic test with very very high probability says the number is probably prime. The probabilistic test aren't probabilistic both ways after all, when my Miller–Rabin says a number is not prime it is a 100% certain of that.
This post has been edited by KarelLodewijk: 28 November 2011  11:29 AM
#22
Re: Ruby Challenge: Prime Numbers
Posted 08 December 2011  03:51 PM
def isPrime(n) for i in 2...n return false if (n%i) == 0 end return true end (2..100).each { x puts x if isPrime(x) }
This post has been edited by Duckington: 08 December 2011  03:52 PM
#23
Re: Ruby Challenge: Prime Numbers
Posted 14 December 2011  06:40 AM
ryuurei, on 01 July 2011  11:01 AM, said:
It might be a little late but reading this again, I noticed that you did implement a prime generating function but not Sieve of Eratosthenes.
The error is that if you find a prime you do trial division on all future primes. What you should be doing is stepping through your list in steps of the prime found and remove all of those.
@DillonSalsman
Your algorithm is sieve, but the delete in your inner loop really throws the complexity skyhigh. Ruby Array is an unsorted container (in your case it is sorted but ruby doesn't know), so delete is an O(n) operation. Ruby arrays are also consecutive in memory so all elements after the delete need to be shifted to the left.
I tried a hand at it myself and came up with this.
require 'mathn' def sieve_prime(n) list = (2..n).to_a sqrt_n_index = Math.sqrt(n)2 for i in 0 .. sqrt_n_index next if (list[i] == nil) (i+list[i]).step(n, list[i]) do j list[j] = nil end end return list.compact end
I've opted for a lazy approach by not actually truncating the list but setting element to nil.
For example in sieve_prime(10), list starts as
[2,3,4,5,6,7,8,9,10]
Next nonnil element is always prime, so 2 is prime, we step through the list from 2+2 by steps of 2 and make those elements nil
[2,3,nil,5,nil,7,nil,9,nil]
Next nonnil element is always prime, so 3 is prime, we step through the list from 3+3 by steps of 3 and make those elements nil
[2,3,nil,5,nil,7,nil,nil,nil]
The next element 5 is larger than sqrt(10) ~= 3.16, so we are done.
This step might not be immediately obvious from the code because I've taken a slightly different approach. Basically I let the index run from 0..sqrt(10)2, so 0..1 in this case, notice how list[sqrt(n)2] initially always contains the last number smaller than sqrt(n)), because sqrt(n) is always rounded down and list[i] initially contains i+2.
Now we return the list without the nils.
This post has been edited by KarelLodewijk: 17 December 2011  02:46 PM
