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 - 32364 Views - Last Post: 14 December 2011 - 06:40 AM

### #16

## Re: Ruby Challenge: Prime Numbers

Posted 01 July 2011 - 11:01 AM

I suppose I'm rather late to the party here but I've been playing with Ruby a lot lately and thought I'd try my hand at my own sieve of Eratosthenes implementation.

### #17

## Re: Ruby Challenge: Prime Numbers

Posted 31 October 2011 - 04:10 PM

Here's a simple solution, written as a method extending Integer.

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.

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

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: #{i-2}" 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

Correction to account for numbers that are less than 2 which, by formal definition, are not prime; and to avoid infinite loops with such input.

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: #{i-2}" return true end end

### #19

## Re: Ruby Challenge: Prime Numbers

Posted 01 November 2011 - 02:32 PM

You should choose a set range of numbers or a specific number to make the speed comparisons fairer. To simply choose some arbitrary, large number is not enough. After all, any number with a small divisor will be found to be non-prime very quickly; even with a naive implementation.

To be more pedantic still: a distinction should be made between

Just my £0.02

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 non-prime. 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:

You should choose a set range of numbers or a specific number to make the speed comparisons fairer. To simply choose some arbitrary, large number is not enough. After all, any number with a small divisor will be found to be non-prime very quickly; even with a naive implementation.

To be more pedantic still: a distinction should be made between

Just my £0.02

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 non-prime. 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 non-primes 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:

You should choose a set range of numbers or a specific number to make the speed comparisons fairer. To simply choose some arbitrary, large number is not enough. After all, any number with a small divisor will be found to be non-prime very quickly; even with a naive implementation.

To be more pedantic still: a distinction should be made between

Just my £0.02

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 non-prime. 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 **Karel-Lodewijk**: 28 November 2011 - 11:29 AM

### #22

## Re: Ruby Challenge: Prime Numbers

Posted 08 December 2011 - 03:51 PM

Decided to start learning Ruby a few hours ago, so here's mine finding the prime numbers up to 100:

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:

I suppose I'm rather late to the party here but I've been playing with Ruby a lot lately and thought I'd try my hand at my own sieve of Eratosthenes implementation.

Spoiler

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 sky-high. 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 non-nil 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 non-nil 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 **Karel-Lodewijk**: 17 December 2011 - 02:46 PM