Prime number function

[cgaceta]

Hey guys. Started C a couple weeks ago and I'm trying to learn how to implement functions. I need to make a function which returns a 1 if its a prime number and 0 if it isn't. This is the pseudo code given to us and I'm having trouble constructing it right.

1) Let variable div represent a possible divisor of x.
2) Set div = 2. Loop.
3) If x is divisible by div then return 0.
4) div++;
5) If div * div > x, return 1, else repeat loop. (go to step 3)

So far, this is what I got:

int isprime (int x)
{
        int div = 2;

        if (x % div ==0)
          return = 0; div++
    
         {
               if ( div * div >  x )
                return = 1;
{
       else

Did I use the return control right to determine if it's a prime number or not? Also, how would I link back to step 3 if div * div > x wasn't true. Thanks again!

[cgaceta]

Okay so I revised my function and came up with this. I'm wondering why the pseudo code step 5 was so confusing. Would this function work the same way as the pseudo code intended it to be?

int isprime(int n)
{
       int div;
 
       if (n == 2)
       return 1;

       for(div = 2; div < n; div++)
       {
              if(n % div == 0)
                return 0;
       }

return 1;

}

[cgaceta]

Okay, so I think I got the basic program down but I need to fine tune it for this next step.

For my main function I need to call isprime from 1 to 1000 using a for loop. If the call isprime(n) returns a 1, I need to print that number. After I've done this, I need to seperate them into columns after every tenth number. This I can't figure out.

Here's my code so far. Any hints would be appreciated.

#include "stdafx.h"

int isprime(int n);


int _tmain(int argc, _TCHAR* argv[])
{
	int x, col = 0;

	for ( x = 1; x <= 1001; x++)
	{
		if( isprime(x) == 1)
			printf("%d  ", x);
		
	}

	
}

int isprime(int n)
{
	int div;

	if(n == 2)
		return 1;

	for(div = 2; div < n; div++)
	{
		if(n % div == 0)
			return 0;
	}

return 1;

}

[yellowSnow]

Do you mean that you want to print 10 primes per line? If so, then use the col variable to count the number of primes that have been output for the current line. Check the count and if it's 10, print the newline character and reset col to 0.

for (x = 1; x <= 1001; x++) {
    if (isprime(x)) {
        printf("%3d  ", x);
        col++;
        if (col == 10) {
            printf("\n");
            col = 0;
        }
    }
}

Also you need to correct your isprime() function to cater for the special case of 1 being passed - 1 is not prime.

Finally, you may want to consider a performance improvement to your prime checking function with regards to the termination condition in the for loop. There is no need to check for divisors up to the number passed - you can just check for divisors between 2 and the square root of the number. For example:

for (div = 2; div <= sqrt(n); div++)

There are other ways to improve the performance of the function but this suggestion is a good start. If you go down this path, you will need to include the math.h header file (for the sqrt() function).

You may also want to consider what to do if a negative number is passed into the isprime() function.

[yellowSnow]

Finally, you may want to consider a performance improvement to your prime checking function with regards to the termination condition in the for loop. There is no need to check for divisors up to the number passed - you can just check for divisors between 2 and the square root of the number. For example:

for (div = 2; div <= sqrt(n); div++)

Errh my bad ... you probably should calculate the square root first and use the result in your for loop:

double root = sqrt(n);
for (div = 2; div <= root; div++) {
    if (n % div == 0)
        return 0;
}

This prevents the square root from being calculated on each iteration of the loop.