# Determining if a number is prime (interview setting)

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

## 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 on other sites
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 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 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 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".

##### 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 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 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 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 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?

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 13
• 30
• 9
• 16
• 12