C - determine if a number is prime

Question

I am trying to come up with a method that takes an integer and returns a boolean to say if the number is prime or not and I don't know much C, anyone care to give me some pointers?

basically how i would do this in C# is like so:

static bool IsPrime(int number)
{
    for (int i = 2; i < number; i++)
    {
      if (number % i == 0 && i != number)
        return false;
    }
    return true;
}

Answer 1

OK, so forget about C. Suppose I give you a number and ask you to determine if it's prime. How do you do it? Write down the steps clearly, then worry about translating them into code.

Once you have the algorithm determined, it will be much easier for you to figure out how to write a program, and for others to help you with it.

edit: Here's the C# code you posted:

static bool IsPrime(int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0 && i != number) return false;
    }
    return true;
}

This is very nearly valid C as is; there's no bool type in C, and no true or false, so you need to modify it a little bit (edit: Kristopher Johnson correctly points out that C99 added the stdbool.h header). Also, prior to C99, you couldn't declare a variable in a for statement, and a lot of compilers still don't support it by default, so let's change that too:

int IsPrime(int number) {
    int i;
    for (i=2; i<number; i++) {
        if (number % i == 0 && i != number) return 0;
    }
    return 1;
}

This is a perfectly valid C program that does what you want. We can improve it a little bit without too much effort. First, note that i is always less than number, so the check that i != number always succeeds; we can get rid of it.

Also, you don't actually need to try divisors all the way up to number - 1; you can stop checking when you reach sqrt(number). Since sqrt is a floating-point operation and that brings a whole pile of subtleties, we won't actually compute sqrt(number). Instead, we can just check that i*i <= number:

int IsPrime(int number) {
    int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

One last thing, though; there was a small bug in your original algorithm! If number is negative, or zero, or one, this function will claim that the number is prime. You likely want to handle that properly, and you may want to make number be unsigned, since you're more likely to care about positive values only:

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

This definitely isn't the fastest way to check if a number is prime, but it works, and it's pretty straightforward. We barely had to modify your code at all!

Answer 2

Try something like this:

int is_prime(int val)
{
  int div;
  for (div = 2; div < val; div++){
    if (val % div == 0)
      return 0;
  }
  return 1;
}

Answer 3

1. Build a table of small primes, and check if they divide your input number.
2. If the number survived to 1, try pseudo primality tests with increasing basis. See Miller-Rabin primality test for example.
3. If your number survived to 2, you can conclude it is prime if it is below some well known bounds. Otherwise your answer will only be "probably prime". You will find some values for these bounds in the wiki page.

Answer 4

Check the modulus of each integer from 2 up to the root of the number you're checking.

If modulus equals zero then it's not prime.

pseudo code:

bool IsPrime(int target)
{
  for (i = 2; i <= root(target); i++)
  {
    if ((target mod i) == 0)
    {
      return false;
    }
  }

  return true;
}

Answer 5

I'm suprised that no one mentioned this.

Use the Sieve Of Eratosthenes

Details:

1. Basically nonprime numbers are divisible by another number besides 1 and themselves
2. Therefore: a nonprime number will be a product of prime numbers.

The sieve of Eratosthenes finds a prime number and stores it. When a new number is checked for primeness all of the previous primes are checked against the know prime list.

Reasons:

1. This algorithm/problem is known as "Embarrassingly Parallel"
2. It creates a collection of prime numbers
3. Its an example of a dynamic programming problem
4. Its quick!

Answer 6

Another option is make a C program (since that's the objective of the exercise) that parses a web page to find if a number is prime.

http://www.numberempire.com/primenumbers.php?action=check&number=49331
http://www.numberempire.com/primenumbers.php?action=check&number=50318795403164923048606009

Answer 7

I would just add that no even number (bar 2) can be a prime number. This results in another condition prior to for loop. So the end code should look like this:

int IsPrime(unsigned int number) {
    if (number <= 1) return 0; // zero and one are not prime
    if ((number > 2) && ((number % 2) == 0)) return 0; //no even number is prime number (bar 2)
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}

Answer 8

add this before your C# code and you're ready to go

typedef enum{false,true} bool;