# Ruby Challenge: Prime Numbers

• (2 Pages)
• 1
• 2

## 22 Replies - 27249 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=c61fe0c7adf4c29eba1303984275c68f&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 xclite

• I wrote you an code

Reputation: 1020
• Posts: 3,568
• Joined: 12-May 09

# Ruby Challenge: Prime Numbers

Posted 09 February 2011 - 10:10 AM

Now that we've had some fun with making our programs tiny, let's do something about making one useful.

The purpose of this challenge is to write a program that tests the primality of a number. Primes are very useful in the area of encryption, have been used on many math challenge sites such as project Euler, and can even be seen in major company recruitment ads.

Testing primes is an interesting exercise. While a naive implementation is very simple, it quickly becomes intractable with larger numbers. In addition, there are several easy optimizations that can dramatically alter your runtime. Finally, there are many different ways to go about testing/finding primes.

Ruby also has a reputation for being slow - I want to see your fastest implementations for determining if a number is prime. Length of the program is not in consideration here; I'd rather see logic spelled out so we can all understand the algorithm.

To see if your program is reasonable, test it with 8-10 digit numbers. Your program/script/function should accept a number and return true or false.

Is This A Good Question/Topic? 3

## Replies To: Ruby Challenge: Prime Numbers

### #2 diego_pmc

Reputation: 81
• Posts: 565
• Joined: 13-May 09

## Re: Ruby Challenge: Prime Numbers

Posted 09 February 2011 - 01:50 PM

This is the first piece of code I ever wrote in Ruby so don't be too harsh. Here's my function:
```def isPrime(number)
if number == 0 or number == 1
return false
end

i = 2
limit = number / i
while i < limit
if number % i == 0
return false
end
i += 1
limit = number / i
end
return true
end
```

Ideally, I shouldn't have to divide the number twice (lines 5 and 9), but I couldn't find a way to check whether a number is integer or not in Ruby. (I only found the to_int_if_whole function, but that's not what I need.) In C++, this (dividing only once) would be written as...

```bool isPrime(long num)
{

if ((num == 0) || (num == 1))
return false;

long double limit = (long double)num;
for (long i = 2; i < (long)limit; ++i) {
limit = (long double)num / (long double)i;
if (limit == (long)limit)
return false;
}
return true;
}
```

However I didn't take into consideration what effect all those type casts have on performance and whether or not they may actually have a greater impact than simply dividing the number twice...

Edit: Added condition to check for 0 and 1.
Edit2: Also, I don't handle negative values in those functions.

This post has been edited by diego_pmc: 10 February 2011 - 04:19 AM

### #3 xclite

• I wrote you an code

Reputation: 1020
• Posts: 3,568
• Joined: 12-May 09

## Re: Ruby Challenge: Prime Numbers

Posted 10 February 2011 - 07:06 AM

Hm that one's interesting - the usual naive approach is to loop an index from 2 up to some limit and reject the number if anything divides evenly. Decreasing the limit each time is something I hadn't used.

I ran your code - check it with 49. Your method returns true. Something to consider is that you can set your limit lower than n/2. Since you check 2 first, there's no reason to check the corresponding factor. Since 2 * x = num, you don't need to check x also - if x divides num, 2 already did and you're out. The highest factor that isn't checked by a lower number is the square root of num.

### #4 diego_pmc

Reputation: 81
• Posts: 565
• Joined: 13-May 09

## Re: Ruby Challenge: Prime Numbers

Posted 10 February 2011 - 10:37 AM

Quote

I ran your code - check it with 49. Your method returns true.

Hmm, I actually wasn't sure if something like that could happen or not, but I couldn't find a number that would give me wrong results (good thing you found one ). The problem seems to be solved if I do either of these two:
```# 1st
while i <= limit
# 2nd
limit = number / i + 1

```

Here's an output of i and limit that shows why:
```i = 3
limit = 16

i = 4
limit = 12

i = 5
limit = 9

i = 6
limit = 8

i = 7
limit = 7

true
```

Quote

Something to consider is that you can set your limit lower than n/2. Since you check 2 first, there's no reason to check the corresponding factor. Since 2 * x = num, you don't need to check x also - if x divides num, 2 already did and you're out. The highest factor that isn't checked by a lower number is the square root of num.

Do you mean that I can simply set the initial limit to num / 2 - 1 or that I should always set the limit to num / i - 1 in every iteration of the loop? The first makes sense, but the second would break the algorithm (see reason why 49 returned true).

### #5 xclite

• I wrote you an code

Reputation: 1020
• Posts: 3,568
• Joined: 12-May 09

## Re: Ruby Challenge: Prime Numbers

Posted 10 February 2011 - 01:10 PM

diego_pmc, on 10 February 2011 - 12:37 PM, said:

Do you mean that I can simply set the initial limit to num / 2 - 1 or that I should always set the limit to num / i - 1 in every iteration of the loop? The first makes sense, but the second would break the algorithm (see reason why 49 returned true).

I'd set the limit to sqrt(num). There is no larger factor than that that isn't already covered. However, I did this in a loop that only incremented the possible factors rather than one that both decreased the limit and incremented the factors. Basically I'd check 2, then every odd after that up to sqrt(num) if I were doing it this way.

There are also other, faster ways to do it but this one's a good way to get thinking about things.
Consider: Sieve of Eratosthenes

### #6 diego_pmc

Reputation: 81
• Posts: 565
• Joined: 13-May 09

## Re: Ruby Challenge: Prime Numbers

Posted 10 February 2011 - 02:52 PM

Quote

I'd set the limit to sqrt(num). There is no larger factor than that that isn't already covered.

Oh, I get it. Thanks for the tip.
Edit: Kinda obvious, when you think about it. =))

Quote

There are also other, faster ways to do it but this one's a good way to get thinking about things.
Consider: Sieve of Eratosthenes

I already knew about the sieve of Eratosthenes, but am I wrong in thinking that's the type of algorithm that would prove efficient when you have to work with a large amount of numbers? :-/

I say that because generating the table (of smaller primes) would actually take more time than simply checking a single number. If, however, you have to check a larger amount of numbers, you could keep the table of smaller primes from the previously checked number so you don't have to generate it every time.

To further optimize it, you could also have the first few primes (up to 1000, for example) hard-coded into the program. A large amount of numbers are bound to be divisible by those if they're not primes. This would also make the algorithm slightly more suitable for when you only have to check a small amount of numbers.

This post has been edited by diego_pmc: 10 February 2011 - 03:04 PM

### #7 xclite

• I wrote you an code

Reputation: 1020
• Posts: 3,568
• Joined: 12-May 09

## Re: Ruby Challenge: Prime Numbers

Posted 10 February 2011 - 03:59 PM

This is true, although the delay is not noticeable between using a loop or the sieve for small numbers, and the sieve overtakes the loop method very quickly.

### #8 ishkabible

• spelling expret

Reputation: 1676
• Posts: 5,836
• Joined: 03-August 09

## Re: Ruby Challenge: Prime Numbers

Posted 10 February 2011 - 10:37 PM

first time using ruby, i think this is as fast as you can get for checking primes as far as complexity goes. i could be wrong however. it should have worst case(n is prime) complexity of O(sqrt(n))

Spoiler

ruby is kinda interesting, it gives me the ease of reading and comfort i feel with Lua but with a more feature rich language, im going to test it to see how fast it is then i will decide howmuch i like it. im gonna make a Dijkstra algorithm class with it and bench it against the others that i have made (i have Dijkstra algorithm written in like 7 different languages )

edit: nope, just 6 it will be 7 when i get ruby done
C++, C#, Java, Lua, Perl, squirrel(another neat language, kinda buggy however)

This post has been edited by ishkabible: 10 February 2011 - 10:45 PM

### #9 xclite

• I wrote you an code

Reputation: 1020
• Posts: 3,568
• Joined: 12-May 09

## Re: Ruby Challenge: Prime Numbers

Posted 11 February 2011 - 07:17 AM

You could make yours more efficient by only iterating over odds after 2 for i
Even though technically the runtime is asymptotically the same.

This post has been edited by xclite: 11 February 2011 - 07:19 AM

### #10 xclite

• I wrote you an code

Reputation: 1020
• Posts: 3,568
• Joined: 12-May 09

## Re: Ruby Challenge: Prime Numbers

Posted 11 February 2011 - 07:39 AM

xclite, on 10 February 2011 - 05:59 PM, said:

This is true, although the delay is not noticeable between using a loop or the sieve for small numbers, and the sieve overtakes the loop method very quickly.

Actually I realized that I misunderstood you - the loop is hard to beat for most primes if you're only doing one check. I also realized my sieve has fallen prey to Ruby convenience - my method is pretty but I think if I removed some of the convenient shortcuts it would be significantly faster.

### #11 ishkabible

• spelling expret

Reputation: 1676
• Posts: 5,836
• Joined: 03-August 09

## Re: Ruby Challenge: Prime Numbers

Posted 11 February 2011 - 10:02 AM

i think your right the odds thing, if you start at 3 then if it's 2 it will never enter the loop and return true because 2 is grater than 1. add 2 to i instead and it should be twice as fast. it would have a complexity of O(sqrt(n)/2-3) witch is pretty damn good if you ask me. also i realized that my current solution is O(sqrt(n)-2) because i start at 2 so that is 2 less iterations from 0. if i start at 3 it trims it by 1 more iteration!

here is the sudo code for the new idea
Spoiler

i cant test it right now because i don't have an interpreter so if i made a mistake sorry, this should have a complexity of O(sqrt(n)-3) when a number is prime and even less when it's not prime. nice idea xclite

edit: tested it with this, i had 1 error but i fixed it(it had '0' as 'o'), it works grate

This post has been edited by ishkabible: 12 February 2011 - 07:45 PM

### #12 Nakor

• Professional Lurker

Reputation: 448
• Posts: 1,504
• Joined: 28-April 09

## Re: Ruby Challenge: Prime Numbers

Posted 12 February 2011 - 01:45 PM

Spoiler

My result on a 12 digit prime was about a half a second

```Start: Sat Feb 12 14:41:10 -0600 2011

100000000951 Is Prime? : true

End: Sat Feb 12 14:41:10 -0600 2011

Elapsed: 0.546001

```

### #13 DillonSalsman

Reputation: 13
• Posts: 144
• Joined: 30-October 07

## Re: Ruby Challenge: Prime Numbers

Posted 03 March 2011 - 11:54 AM

Sieve of Eratosthenes in action:
```def primesUpto(max)
num = [1, 2, 3]

return [] if max < 1

if max < 3;
(3 - max).times do num.pop end
return num
end

#push all the odds, no need to waste cycles stripping evens
num.push(num[-1] + 2) until (num[-1] + 2) > max

#for each prime from 3 upto sqrt(max)
#strip n * currentPrime  for n from 2 upto max/currentPrime
i = 2; until num[i] >= (Math.sqrt(max).floor)
puts "Stripping multiples of #{num[i]}"
((max/num[i]-2).floor).times do |j|
(num.delete((num[i])*(j+2)))
end; i+=1
end; return num
end

puts primesUpto(50000)

```

Wasn't sure if we were playing code golf or not. My original answer was much less readable and much more compact.

### #14 xclite

• I wrote you an code

Reputation: 1020
• Posts: 3,568
• Joined: 12-May 09

## Re: Ruby Challenge: Prime Numbers

Posted 03 March 2011 - 12:12 PM

No cold gulf - good posts all

### #15 Karel-Lodewijk

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

## Re: Ruby Challenge: Prime Numbers

Posted 30 June 2011 - 03:26 PM

All suggestions here assume that testing if a number is prime requires finding denominators. Factorization is hard, determining if a number is prime however is not necessarily.

There is another class of probabilistic algorithms to determine if a number is prime. Implemented here is the Miller–Rabin primality test. http://en.wikipedia...._primality_test

I use k = 20, This means:
• If the algorithm says the number is not prime, it is definitely not prime.
• If the algorithm says the number is probably prime, then the number is prime with probability 1-(0.25^k). So we are 99.99999999990905% certain the number is prime, a probability that can easily be increased by increasing k.

The complexity only relies on k and length of the number n. O(k*log(n)^3). Not to be confused with the complexity ishkabible is using.

Writing it is not too hard. Understanding why it works however is not so easy and stooled in number theory.

output:
100000000951 is probably prime
Time elapsed 1.2526512145996094 milliseconds

359334085968622831041960188598043661065388726959079837 is probably prime
Time elapsed 8.954048156738281 milliseconds

```require 'benchmark'

#caclculates base**exponent % modulus but in such a way that the number doesn't grow too large and number of operations stays reasonably small
def modular_pow(base, exponent, modulus)
result = 1
while exponent > 0 do
if (exponent & 1) == 1 then
result = (result * base) % modulus
end
exponent = exponent >> 1
base = (base * base) % modulus
end
return result
end

def isPrime(n)
if n < 5 then
if n == 2 || n == 3 then
return True
else
return False
end
end

#writing n-1 as 2^s * d (d odd)
s = 0
d = n - 1
while (d%2 == 0) do
d=d/2
s=s+1
end

20.times do
a = Random.rand(n-4) + 2 #random number on (2,n-2)
#x = a**d % n
x = modular_pow(a,d,n)
if (x==1 || x==n-1) then
next
end
for r in 1 .. s-1 do
x = modular_pow(x,2,n)
if x == 1 then
return false
end
if x == n-1 then
stop = true
break;
end
end
if (stop) then
next;
end
return false
end
return true;
end

n = gets.to_i
time = Benchmark.realtime {
if isPrime(n) then
print n, " is probably prime\n"
else
print n, " is not prime\n"
end
}
puts "Time elapsed #{time*1000} milliseconds"

```

This post has been edited by Karel-Lodewijk: 30 June 2011 - 03:35 PM