Jimmy - 6 months ago 33

C 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; would anyone care to give me some pointers?

Basically, I would do this in C# like this:

`static bool IsPrime(int number)`

{

for (int i = 2; i < number; i++)

{

if (number % i == 0 && i != number)

return false;

}

return true;

}

Answer

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). Since some people don't have access to a C99 environment (but you should use one!), let's make that very minor change:

```
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!