Find out if a number is prime [duplicate]

This question already has an answer here:

I read that every prime number is of the form $6k\pm1$, is this a correct approach to find out if a number is prime?

auto isPrime = [&](int num) {
if (num == 0 || num == 1)
return false;
if (num == 2 || num == 3)
return true;
if ((num - 1) % 6 == 0 || (num + 1) % 6 == 0)
return true;
else
return false;
};

marked as duplicate by Henning Makholm, hardmath, Shailesh, Leucippus, JMPJun 7 '16 at 3:06

• A correct statement is that every prime greater than $3$ is of that form (since $2$ and $3$ are not). But this is only checking that your number is not divisible by $2$ or $3$, so it is a start (on trial division) to showing a number is prime, but not the final word. For example $25$ is of the form $6k+1$, but $25$ is not prime. – hardmath Jun 6 '16 at 15:37
• Not at all. $6\cdot4+1$ isn't prime. You are testing if a number is of the form $6k\pm1$ or is $2$ or $3$, nothing more. – Yves Daoust Jun 6 '16 at 15:37
• It is true that every prime number other than $2$ and $3$ is of the form $6k\pm 1$. That is if "prime" then "of the form $6k\pm 1$." However, what you seem to implement is more the converse or even an if and only if. – quid Jun 6 '16 at 15:37
• Every prime greater than $3$ is of the form $6k\pm1$, but not every number of the form $6n\pm1$ is prime. You haven't tested whether the numbers are actually prime... – abiessu Jun 6 '16 at 15:38
• What you have implemented is a correct way of determining if a number is $2$, $3$ or of the form $6k\pm 1$, but that does not make a number prime. – Henrik Jun 6 '16 at 15:39

No, and the informal argument is: that would be way too simple. Proving there is an efficient algorithm to check if a given number is prime was a big breakthrough in computational complexity, and only happened in 2002.

Your algorithm will accept $2,3$, and any number of the form $6k\pm 1$; but while every prime number is of this form, there are many numbers of this form that are not prime. E.g., $25$.

If you are looking for a deterministic algorithm (running in polynomial time) checking whether a given number is prime, I suggest you read about the AKS algorithm.

(Note that there are much more efficient randomized algorithms for doing so, e.g. Miller—Rabin; i.e., they will give the right answer with very high probability, but there is a slight chance they'll err.)

• Note that "efficient" and "polynomial-time" above mean "polynomial in the size of the input." That is, to test whether a given number $n\geq 1$ is prime, the input size is roughly $\log_2 n$, and so the goal is to run in time $O((\log n)^c)$ for some constant $c>0$. – Clement C. Jun 6 '16 at 15:56
• The are much more efficient non-randomized deterministic algorithms if you restrict your inputs to those computable in under a billion years. There are also much more efficient algorithms that use randomness with no chance of error. Contrast Las Vegas (e.g. ECPP) with Monte Carlo (e.g. Miller-Rabin) algorithms. – DanaJ Jun 8 '16 at 5:05

I can give you a easy trick

Step 1: Check nearest perfect square number of given number

for example,Let given number is $131$.

So,nearest perfect square number is $144(12^2)$

Step 2: Find prime numbers $\lt 12$ i.e $2,3,5,7,11$

Step 3: Check divisibilty of $131$ by $2,3,5,7,11$

If it's not divisible by any of the number.Then it is prime.

So,$131$ is prime

• For very small numbers, this algorithm is best. For large numbers, there are much more efficient methods , as Clement points out. – Peter Jun 6 '16 at 15:52
• This primality testing "trick" is called trial division. – hardmath Jun 6 '16 at 15:54
• agreed,this is useful for small numbers,but this is highly useful in numerical aptitude or competitive exams – Hailey Jun 6 '16 at 15:55