• Advertisement
Sign in to follow this  

Determining if a number is prime (interview setting)

This topic is 2297 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
Ah, primes are fun!

Define a[0]:=3, a[1]:=0, a[2]:=2, a[n+3]:= a[n]+a[n+1] for all n>=0. If you want to know if a number is prime, check if p divides a

(this can be done about as fast as checking Fermat's little theorem).

a[2]%2 = 2%2 = 0 <- prime
a[3]%3 = 3%3 = 0 <- prime
a[4]%4 = 2%4 = 2
a[5]%5 = 5%5 = 0 <- prime
a[6]%6 = 5%6 = 5
a[7]%7 = 7%7 = 0 <- prime
a[8]%8 = 10%8 = 2
a[9]%9 = 12%9 = 3
a[10]%10 = 17%10 = 7
a[11]%11 = 22%11 = 0 <- prime
a[12]%12 = 29%12 = 5
a[13]%13 = 39%13 = 0 <- prime
...

This works for all primes (can you prove it?) and although the converse is not true, it's still a reasonably fast check, if implemented correctly. The smallest example of a composite number for which it fails is a 5-digit perfect square. :)

Share this post


Link to post
Share on other sites
I think context is important -- If its a random coding position, then the purpose of this question is not to determine how much you know about determining primes, but to have an excuse to show your thought process on a problem that everyone understands and can be described without ambiguity in basically one sentence. On the other hand, if the job is related to cryptography directly, or very math-oriented in general, then the interviewer probably expects a more learned answer.

If the former, then going straight to the most-clever answer you know of can be a detriment -- a good rule of thumb that I usually use to to summarize and explain the naive or straight-forward approach, and then to impliment (assuming whiteboard) the best approach you know which is a) suitably concise to demonstrate/explain, and b) which you have a comfortable understanding of. Then, if you know of even better methods, mention them, but only if you've got at least a basic idea of how they work. There's really few worse things you can do in an interview than allow your reach to exceed your grasp -- a good interviewer will ask follow up questions, or even challenge you on the efficacy of your solution (even if you've done it right) basically just to see if you are sure of yourself, and that you know the approach well enough to defend it, not just replicate it. If you choose a solution that is beyond you, and are unable to defend it, it will often-times look worse than had you chosen the next best solution and knowing it beyond reproach.


A good interview, especially a first/only interview, is about 20% what you know, 50% how you think, and 30% how you fit. A good skill to have is distinguising between the "what you know" questions and the "how you think" ones (and often times that a question is about both) -- but if you can't tell, assume its a "how you think" question. I'd personally choose someone who I was sure could think and reason well over someone who only demonstrated memorization of wrote fact any day of the week.

Share this post


Link to post
Share on other sites
I remember writing a program for finding large values of prime numbers. I just recorded each one I found and divided new numbers by each prime to see if it was a prime number. If the program had to be done more memory efficiently, I'm afraid I have to resort to brute force. I have no idea what the Miller-Rabin test is although I know what flt is.

Share this post


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

  • Advertisement