Function to Determine if Int is Prime

This is a discussion on Function to Determine if Int is Prime within the C Programming forums, part of the General Programming Boards category; I am supposed to write a function that determines if a number is prime or not. I return 1 if ...

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    23

    Function to Determine if Int is Prime

    I am supposed to write a function that determines if a number is prime or not. I return 1 if it is prime and 0 if it is not.

    This is what I have so far:

    Code:
    int isPrime ( int number )
    {
    	int i = 2;
    
    	for(i=2; i<number ; i++)
    	{
    		if((number&#37;i) == 0)
    		{
    		return 0;
    		}
    		else
    		{
    			return 1;
    		}
             }
    }
    I'm not quite sure what's wrong with that.


    Thanks

    Edit: The function does work but I get the compiler warning, "control reaches end of non-void function" how could I get rid of that.

    Edit Again: I figured it out, I just added an integer x and in one if statement I did x=0 rather than return 0 and for the other I did x = 1 rather than return 1, then at the end of the function I had return x.

    Thanks anyways.
    Last edited by Adrian; 11-21-2007 at 10:09 PM.

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,243
    Quote Originally Posted by Adrian View Post
    Edit Again: I figured it out, I just added an integer x and in one if statement I did x=0 rather than return 0 and for the other I did x = 1 rather than return 1, then at the end of the function I had return x.
    Your real problem is that you "return 1;" when there is a non-zero remainder. That's obviously not right, you need to check ALL the values. Instead of returning 1, just don't do anything at all. And at the end of the function, outside the for-loop, return 1.

    You have effectively accomplished the same thing by introducing this "x" variable but it's not necessary, and still wrong. Once x has been set to 0, it must never be set back to 1, since you've already proven the number isn't prime. And there is no point continuing the loop once this happens.

    What does your current code look like?

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    23
    Code:
    int isPrime ( int number )
    {
    
    	int x;
    
    	int i = 2;
    
    	for(i=2; i<number ; i++)
    	{
    		if((number&#37;i) == 0)
    		{
    		x = 0;
    		}
    		else
    		{
    		x = 1;
    		}
    	}
    
    	return x;
    }
    But if there is a remainder that is 0 when the number is divided by anything between 1 and itself doesn't that mean it's not prime?
    Last edited by Adrian; 11-21-2007 at 10:25 PM.

  4. #4
    Registered User
    Join Date
    Oct 2007
    Posts
    23
    This is what it should be:

    Code:
    int isPrime ( int number )
    {
    
    	int x = 1;
    
    	int i = 2;
    
    	for(i=2; i<number ; i++)
    	{
    		if((number&#37;i) == 0)
    		{
    		x = 0;
    		}
    
    	}
    
    
    	return x;
    }
    That else statement in the for loop was messing things up.

    I'm going to go now, but thanks for your help, the function does work now.

    Thanks!
    Last edited by Adrian; 11-21-2007 at 10:32 PM.

  5. #5
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Here's a tip.

    Let's say the number passed to your program is 29 - a primer number, but we don't know that yet. The current logic will test all numbers between 2 and 28. That's wasteful, because 29/2 (or generically, 1/2 of the passed number) is the largest value you ever need to check. Run some other samples through, you'll see what I mean.

    Todd

  6. #6
    Ex scientia vera
    Join Date
    Sep 2007
    Posts
    478
    Quote Originally Posted by Todd Burch View Post
    Here's a tip.

    Let's say the number passed to your program is 29 - a primer number, but we don't know that yet. The current logic will test all numbers between 2 and 28. That's wasteful, because 29/2 (or generically, 1/2 of the passed number) is the largest value you ever need to check. Run some other samples through, you'll see what I mean.

    Todd
    Isn't it the square root of the max number the largest number you have to check?

  7. #7
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    You could do that too.

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,558
    > I return 1 if it is prime and 0 if it is not.
    So you return 1 ONLY if all the tests pass, not the first test.
    Your first attempt was isOdd(), not isPrime().
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Compiling sample DarkGDK Program
    By Phyxashun in forum Game Programming
    Replies: 6
    Last Post: 01-27-2009, 02:07 AM
  2. Replies: 48
    Last Post: 09-26-2008, 03:45 AM
  3. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  4. Replies: 1
    Last Post: 10-27-2006, 01:21 PM
  5. Converted from Dev-C++ 4 to Dev-C++ 5
    By Wraithan in forum C++ Programming
    Replies: 8
    Last Post: 12-03-2005, 06:45 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21