Jump to content
  • Advertisement
Sign in to follow this  
Darkbouncer4689

Determining if a number is prime (interview setting)

This topic is 2596 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So a question I see a lot of people post as having gotten in an interview setting is "Write a function to determine if a number is prime"

The brute force method would be to of course divide some number N by all numbers from 2 to N-1 (easier to implement by checking if N % i == 0).
A slightly smarter approach is to do the same method above but only up to floor(sqrt(N)) which can cut down a good bit.

How many people have broken out the method of determining that N is prime by some extremely high probability using Fermat's little theorem and Miller-Rabin test? I only know of it from cryptography, but it's the only reasonable time complexity algorithm for very large values of N. Wonder if that's overkill for an interview question >_>

Share this post


Link to post
Share on other sites
Advertisement
I don't know the fermats theorem nor the miller-rabin test, but you can do this:

- Check if the number is even or odd. Even numbers are never prime as they can be devided by 2 (exception: 2)

- Numbers whose last digit is 5 are not prime (exception: 5).

There are two more of these rules I think, knowing these is enough to determine a prime numner. I think the additional rules have something to do with divinh by 3 and 6, but I'm not sure..

Share this post


Link to post
Share on other sites
It's probably overkill for an interview question if you're expected to code it! I wouldn't expect many to have even heard of the Sieve of Atkin, and I've never seen an implementation of it. But if it's just a discussion of theory then if you're told that the number can be big, then it would certainly be a bonus to be able to mention techniques such as Miller-Rabin.

Otherwise, trial division by primes < sqrt(n), or even Sieve of Eratosthenes, would be fine answers I expect.

Share this post


Link to post
Share on other sites
Wow, these two techniques were never even mentioned in my cryptography class... in which finding large primes is important to multiple cryptography algorithms.

Thanks for the name drop, I'm going to check these out =)

Share this post


Link to post
Share on other sites

The sieve of Erathostenes is a correct answer that can be coded on the fly. My answer would be that, and mention deterministic polynomial time tests for an hypothetical "phase 2".


This.

I would expect you to stop at floor(sqrt(n)) and know that there are better algorithms for larger numbers. If you went to n-1 or n/2 that would be a red flag. If you thought that was the end-all be-all of algorithms, that would be a smaller red flag (depending on the position). If you knew about the quadratic or number field sieve bonus points (and a follow up question to describe the algorithms to me in layman's terms).

Share this post


Link to post
Share on other sites
Fermat's theorem is pretty simple, though requires a little modification to be completely accurate.


public bool isPrime()
{

bignum a = new bignum();
Random rand = new Random();
bool prime = true;

a.genRandomBits(dataLength * 16, rand);

if (!(modexp(a, this - 1, this) == 1))
prime = false;

return prime;
}


that is directly out of my code from cryptography class. modexp(a,b, c) being modular exponentiation: a^b % c.

this is also done on a arbitrary size number that this is put into, hence the generation of random bits instead of a random number.

Share this post


Link to post
Share on other sites
that is directly out of my code from cryptography class


You probably don't want to be allocating a Random inside the function. Consider what happens if you call isPrime in a loop. (Just a side point.)

Share this post


Link to post
Share on other sites

[quote name='Hartra34' timestamp='1320771577' post='4881807']that is directly out of my code from cryptography class


You probably don't want to be allocating a Random inside the function. Consider what happens if you call isPrime in a loop. (Just a side point.)
[/quote]

true, though in this case, the random or the reuse of the random really doesn't matter. Theoretically it could be a constant off the top of my head, I just like using random better.

Share this post


Link to post
Share on other sites

Fermat's theorem is pretty simple, though requires a little modification to be completely accurate.


public bool isPrime()
{

bignum a = new bignum();
Random rand = new Random();
bool prime = true;

a.genRandomBits(dataLength * 16, rand);

if (!(modexp(a, this - 1, this) == 1))
prime = false;

return prime;
}


that is directly out of my code from cryptography class. modexp(a,b, c) being modular exponentiation: a^b % c.

this is also done on a arbitrary size number that this is put into, hence the generation of random bits instead of a random number.


So...

What is the run-time and space complexity of this algorithm?

What if a == 0? What if it's -1?

How is modulo defined and how is it calculated for negative numbers? What about other languages and architectures, such as built in % operators or idiv?

How could one implement such an algorithm without bignum class?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!