# Ruby Challenge: Prime Numbers

• (2 Pages)
• 1
• 2

## 22 Replies - 26112 Views - Last Post: 14 December 2011 - 06:40 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=215027&amp;s=2f0315aec548d82a3baea2f754c0a09f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #16 ryuurei

Reputation: 1
• Posts: 5
• Joined: 09-March 11

## 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.

```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

```

### #17 jace427

Reputation: 2
• Posts: 7
• Joined: 31-October 11

## 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.

```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:
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 jace427

Reputation: 2
• Posts: 7
• Joined: 31-October 11

## 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 RetardedGenius

• ﻿>>──(Knee)──►

Reputation: 126
• Posts: 555
• Joined: 30-October 10

## 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 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 jace427

Reputation: 2
• Posts: 7
• Joined: 31-October 11

## 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 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 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

## 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 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 Duckington

Reputation: 172
• Posts: 614
• Joined: 12-October 09

## 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 Karel-Lodewijk

Reputation: 454
• Posts: 864
• Joined: 17-March 11

## 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