1
$\begingroup$

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;
    };
$\endgroup$

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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. $\endgroup$ – hardmath Jun 6 '16 at 15:37
  • 4
    $\begingroup$ 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. $\endgroup$ – Yves Daoust Jun 6 '16 at 15:37
  • $\begingroup$ 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. $\endgroup$ – quid Jun 6 '16 at 15:37
  • $\begingroup$ 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... $\endgroup$ – abiessu Jun 6 '16 at 15:38
  • 2
    $\begingroup$ 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. $\endgroup$ – Henrik Jun 6 '16 at 15:39
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Clement C. Jun 6 '16 at 15:56
  • $\begingroup$ 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. $\endgroup$ – DanaJ Jun 8 '16 at 5:05
1
$\begingroup$

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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.