1

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;
    };
Michael Hardy
  • 1
Dean
  • 175
  • 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 06 '16 at 15:37
  • 4
    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. –  Jun 06 '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 06 '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 06 '16 at 15:38
  • 2
    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 supports the community Jun 06 '16 at 15:39
  • Your condition is necessary (for n > 3) but not sufficient. It's limiting to those numbers not divisible by 2 or 3. – DanaJ Jun 08 '16 at 05:09

2 Answers2

1

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

Clement C.
  • 67,323
  • 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 06 '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 08 '16 at 05:05
1

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

Hailey
  • 1,020