Any idea on why this program is returning that 987 is a prime number (when it is not a prime number)-CodePudding

I think the problem is with the for-loop but I cannot understand it. This is an assignment in school that I only should use for-loops and if statements to solve!

#include <stdio.h>
int is_prime(int n){
  for (int i=2;i<n;i  ){
    if (n%i!=0){
      return 1;
    }
    else{
      return 0;
    };
  };
}

int main(void){
  printf("%d\n", is_prime(11));  // 11 is a prime.      Should print 1.
  printf("%d\n", is_prime(383)); // 383 is a prime.     Should print 1.
  printf("%d\n", is_prime(987)); // 987 is not a prime. Should print 0.
}

CodePudding user response：

For starters the null statement after the if statement and the for loop itself

  for (int i=2;i<n;i  ){
    if (n%i!=0){
      return 1;
    }
    else{
      return 0;
    };
    ^^^
  };
  ^^^

is redundant.

Due to the if statement the for loop is interrupted as soon as either n % i is not equal to 0 or is equal to 0. So in general the behavior of the function does not depend on whether the passed number is prime or not prime.

If you will move the return statement

return 1;

outside the loop as others advised nevertheless the function will be still incorrect. It will show that 0 and 1 are prime numbers while they are not.

Also the condition of the loop makes the loop inefficient at least because it is clear before entering the loop that any even number except 2 is not a prime number.

Pay attention to that the function parameter should have unsigned integer type.

The function can be defined the following way

#include <stdio.h>

int is_prime( unsigned long long int n )
{
    int prime = n % 2 == 0 ? n == 2 : n != 1;
 
    for ( unsigned long long int i = 3; prime && i <= n / i; i  = 2 )
    {
        prime = n % i != 0;
    }

    return prime;
}

int main(void) 
{
    printf( "%d\n", is_prime( 11 ) );
    printf( "%d\n", is_prime( 383 ) );
    printf( "%d\n", is_prime( 987 ) );
  
    return 0;
}

The program output is

1
1
0

CodePudding user response：

The problem is return 1 inside the loop. When you find one i that is not a factor of n, you assume n to be prime. But you have to ensure that all i are not a factor of prime, so the return 1 must be placed after the loop. However, that would cause numbers < 2 to be considered prime, as they do not enter the loop at all. Therefore, you also have to add an additional if at the beginning.

By the way: Every divisor of n (expect n itself) must be <= sqrt(n), therefore you can speed up your function quite a bit.

#include <math.h>

int is_prime(int n) {
  if (n < 2)
    return 0;
  int max_divisor = sqrt(n);
  for (int i = 2; i <= max_divisor; i  ) {
    if (n % i == 0)
      return 0;
  }
  return 1;
}

CodePudding user response：

Problem: return statement

  return 1;
}
else{
  return 0;

It causes the loop to exit then and there. In your case too, it exits as soon as the first '1' is achieved.

Solution: Instead you should try to store the values in a variable and compare with '1' or '0' at the end of loop