22 Replies  20392 Views  Last Post: 14 December 2011  06:40 AM
#1
Ruby Challenge: Prime Numbers
Posted 09 February 2011  10:10 AM
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 810 digit numbers. Your program/script/function should accept a number and return true or false.
Replies To: Ruby Challenge: Prime Numbers
#2
Re: Ruby Challenge: Prime Numbers
Posted 09 February 2011  01:50 PM
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
Re: Ruby Challenge: Prime Numbers
Posted 10 February 2011  07:06 AM
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
Re: Ruby Challenge: Prime Numbers
Posted 10 February 2011  10:37 AM
Quote
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
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
Re: Ruby Challenge: Prime Numbers
Posted 10 February 2011  01:10 PM
diego_pmc, on 10 February 2011  12:37 PM, said:
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
Re: Ruby Challenge: Prime Numbers
Posted 10 February 2011  02:52 PM
Quote
Oh, I get it. Thanks for the tip.
Edit: Kinda obvious, when you think about it. =))
Quote
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) hardcoded 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
Re: Ruby Challenge: Prime Numbers
Posted 10 February 2011  03:59 PM
#8
Re: Ruby Challenge: Prime Numbers
Posted 10 February 2011  10:37 PM
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
Re: Ruby Challenge: Prime Numbers
Posted 11 February 2011  07:17 AM
Even though technically the runtime is asymptotically the same.
This post has been edited by xclite: 11 February 2011  07:19 AM
#10
Re: Ruby Challenge: Prime Numbers
Posted 11 February 2011  07:39 AM
xclite, on 10 February 2011  05:59 PM, said:
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
Re: Ruby Challenge: Prime Numbers
Posted 11 February 2011  10:02 AM
here is the sudo code for the new idea
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
Re: Ruby Challenge: Prime Numbers
Posted 12 February 2011  01:45 PM
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
Re: Ruby Challenge: Prime Numbers
Posted 03 March 2011  11:54 AM
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
Re: Ruby Challenge: Prime Numbers
Posted 03 March 2011  12:12 PM
#15
Re: Ruby Challenge: Prime Numbers
Posted 30 June 2011  03:26 PM
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 n1 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(n4) + 2 #random number on (2,n2) #x = a**d % n x = modular_pow(a,d,n) if (x==1  x==n1) then next end for r in 1 .. s1 do x = modular_pow(x,2,n) if x == 1 then return false end if x == n1 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 KarelLodewijk: 30 June 2011  03:35 PM
