[xclite]

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.

[diego_pmc]

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

[xclite]

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.

[diego_pmc]

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

[xclite]

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

[diego_pmc]

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

[xclite]

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.

[ishkabible]

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

def isPrime(x)
	max = Math.sqrt(x)
	for i in 2 .. max
		if x%i==0 then
			return false
		end
	end
	return x>1
end

for i in 0 .. 100
	if isPrime(i) then
		puts "#{i} is prime"
	end
end

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

[xclite]

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

[xclite]

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.

[ishkabible]

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

def isPrime(x)
	if x%2==0 and x>2 then
		return false
	end
	max = Math.sqrt(x+1)
	i=3
	while i<max
		if x%i == 0 then
			return false
		end
		i+=2
	end
	return x>1
end

for i in 0 .. 100
	if isPrime(i) then
		puts "#{i} is prime"
	end
end

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

[Nakor]

Spoiler

class MyMath

	def self.IsPrime(stop)
		return false if stop == 0 or stop == 1
		max = Math.sqrt(stop)
		return false if stop != 2 and stop%2 == 0
		3.step(max, 2) { |i|
			return false if stop%i == 0
		}
		return true;
	end
	
	def self.GetPrimes(start, stop)
		for i in start..stop
			puts i if MyMath.IsPrime(i)
		end
	end
end

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

[DillonSalsman]

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.

[xclite]

No cold gulf - good posts all

[Karel-Lodewijk]

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