-3

I needed a method to check whether given number is prime or not. I searched on internet and I found different functions but they were complex. So, I designed my own method for checking whether the number is prime or not. It is working for me. I just wanna know if it is correct or not. The code is given below:

bool IsPrime(int n)
{
    for (int i = 2; i <= 7; i++)
    {
        if (i < n && n % i == 0)
        {
            return false;
        }
        if (i == n)
        {
            return true;
        }
    }
    return true;
}
Zohaib Aslam
  • 585
  • 1
  • 4
  • 15
  • 4
    Why 7? Don't you need to test each value of `i` up to and including the square root of `n`? – Patricia Shanahan Jan 27 '15 at 17:03
  • 1
    call `IsPrime(121)` and see if you think it's right or not. – D Stanley Jan 27 '15 at 17:03
  • 1
    If you want to know whether it's correct, unit test it or prove it. – chris Jan 27 '15 at 17:03
  • 1
    You'll want to test beyond 7. This will think 11 is not prime. – Mike Seymour Jan 27 '15 at 17:03
  • 121 is not a prime, but that function will return true. It only checks for primes with a divisor between 2 and 7. I think if you check for divisors between 2 and sqrt(n), it'll work, but very inefficiently. – Ask About Monica Jan 27 '15 at 17:04
  • 11 is prime, last statement will return true for 11 @MikeSeymour – Zohaib Aslam Jan 27 '15 at 17:04
  • also: test for i=2 before the loop, then do `for(int i=3; i < sqrtOfN; i+=2)` – DrKoch Jan 27 '15 at 17:04
  • 1
    The logic of your function says that a number is prime if it is not divisible by any number from 2 through 7. That's not the definition of prime. As others have said, 121 is not divisible by 2, 3, 4, 5, 6, or 7, yet is still not prime. – Joseph Mansfield Jan 27 '15 at 17:04
  • @ZohaibAslam: Sorry, I misread the final return. In that case, as others said, it'll think 11^2 (121) is not prime. Either way, you need to check at least all prime numbers up to `sqrt(N)`, not just up to 7. – Mike Seymour Jan 27 '15 at 17:06
  • thank you all of you :) i got the point. i posted this question because i wasn't sure about whether this will work correctly or not, and now i know it will not work – Zohaib Aslam Jan 27 '15 at 17:08
  • possible duplicate of [Program to find prime numbers](http://stackoverflow.com/questions/1510124/program-to-find-prime-numbers) – phillip Jan 27 '15 at 17:17
  • Bit late to the game here, but see [my solution](http://stackoverflow.com/a/38985869/3504007) below for the "proper" way to check if any number is a prime - quickly, using Euler's Theorem. I have simplified it into a copy paste method which you can recycle. – Kraang Prime Aug 16 '16 at 23:22

2 Answers2

0

Short answer: No, it is not correct.

Kind answer: Here's working code:

bool IsPrime(int n)
{
    if (n <= 1) return false;      // .. , -1, 0, 1
    if (n == 2) return true;        // 2
    if (n % 2 == 0) return false;    // 4, 6, 8, ...
    int sqrt = (int)Math.Sqrt(n); // largest possible factor        
    for (int i = 3; i <= sqrt; i+=2)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

Remark: There are many algorithm that work better, faster, etc...

Edit

Using @Blastfurnace's idea and some more here an optimized version:

bool IsPrime(int n)
{
    if (n <= 1) return false;      // .. , -1, 0, 1    
    if (n % 2 == 0) return (n==2);    // 2 and even numbers
    if (n % 3 == 0) return (n==3);    // 3 and divisible by 3
    if (n % 5 == 0) return (n==5);
    if (n % 7 == 0) return (n==7); // the magic 7 from OP 
    if (n < 11) return false;
    // calc sqrt as rare as possible, its expensive
    int sqrt = (int)Math.Sqrt(n); // largest possible factor  
    // skip 9, already done with n%3
    for (int i = 11; i <= sqrt; i+=2) if (n % i == 0) return false;

    return true;
}

This should save some CPU cycles.

DrKoch
  • 9,556
  • 2
  • 34
  • 43
  • 1
    And it does (incorrectly) think that 1 is. Both 1 and 2 will need special cases. – Mike Seymour Jan 27 '15 at 18:04
  • Another way to special case multiples of 2 is to say `if (n % 2 == 0) return (n == 2);`. Then you won't test odd numbers to see if they're equal to 2. – Blastfurnace Jan 28 '15 at 16:02
  • @Blastfurnance Well - this replaces a few cycles in the CPU with quite some cycles in my brain to understand my code... ;) – DrKoch Jan 28 '15 at 16:05
0

From the definition of a prime number, "An integer greater than one is called a prime number if its only positive divisors (factors) are one and itself.", 0 and 1 are not prime numbers.

Correction of DrKoch's answer:

bool IsPrime(int n)
{
    if( n == 0 || n == 1)
       return false;
    else if(n == 2)
       return true;
    else if(n%2 == 0)
       return false;
    else {
       int sqrt = (int)Math.Sqrt(n);

       for (int i = 3; i <= sqrt; i+=2)
       {
           if (n % i == 0)
              return false;
       }

       return true;
    }
}
fayez
  • 71
  • 2