Primality Tester

This is a discussion on Primality Tester within the C Programming forums, part of the General Programming Boards category; I'm trying to create a program that will determine whether the input number is a prime number. I've hit a ...

  1. #1
    Registered User
    Join Date
    Sep 2008
    Posts
    3

    Primality Tester

    I'm trying to create a program that will determine whether the input number is a prime number. I've hit a roadblock though. Here's the code.

    Code:
    #include<stdio.h>
    
    int main(void)
    {
    
    	int number;
    	int count;
    	int divisor = 2;
    	
    	printf("Input number for primality testing\n");
    	scanf("d",number);
    	
    	while (divisor < number/2) {	
    		if (number % divisor == 0) {
    			break;	
    		}
    		else {
    			divisor++;
    		}
    	}
    
    	if (divisor >= number/2) {
    		printf("Number is prime\n");
    	}
    	else {
    		printf("Number is not prime\n");
    	}
    	return 0;
    }
    The problem I keep getting is that the program never reaches the "else" to increment the divisor. I can't figure out why. Can anyone help?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I hope you don't have "scanf("d", number);" actually in your code?

  3. #3
    Registered User
    Join Date
    Sep 2008
    Posts
    3
    Wow, never mind, *facepalm*, a simple scanf problem.

    Code:
    #include<stdio.h>
    
    int main(void)
    {
    
    	int number;
    	int count;
    	int divisor = 2;
    	
    	printf("Input number for primality testing\n");
    	scanf("%d",&number);
    	
    	while (divisor < number/2) {	
    		if (number % divisor == 0) {
    			break;	
    		}
    		else {
    			divisor++;
    		}
    	}
    
    	if (divisor >= number/2) {
    		printf("Number is prime\n");
    	}
    	else {
    		printf("Number is not prime\n");
    	}
    	return 0;
    }

  4. #4
    Registered User
    Join Date
    Sep 2008
    Posts
    3
    &tabstop

    Yeah, I noticed that right after I posted, kind of embarrassing to make such a simple error.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Yeah, it seems to be endemic today. ("it" being scanf things.) But you caught it, and that's a good thing.

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,439
    1. Use gcc as your compiler, like cygwin or mingw, or one of the many IDEs which come with it, like dev-c++ and code::blocks. Or even your default compiler for Linux.

    2. Use these flags
    gcc -W -Wall -ansi -pedantic -O2 prog.c
    It will tell you a lot, including whether your printf/scanf type function format strings make any sense.
    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.

  7. #7
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Does your code really prove that a number is prime? That is the question of the day (Note: I don't ask such questions for no apparent reason).

  8. #8
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by master5001 View Post
    Does your code really prove that a number is prime? That is the question of the day (Note: I don't ask such questions for no apparent reason).
    Do you have a counterexample in mind, other than 1?

  9. #9
    Budding Synth Programmer samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Trefforest
    Posts
    368
    Your while condition will most likely make the second if fail. You correctly exit the loop when you discover it's not prime, so at that point why not just set a flag (bool isPr or something), then test that?
    MSVC++ 6.0

  10. #10
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Quote Originally Posted by samGwilliam View Post
    Your while condition will most likely make the second if fail. You correctly exit the loop when you discover it's not prime, so at that point why not just set a flag (bool isPr or something), then test that?
    Or Even better yet:

    Code:
    #include<stdio.h>
    
    int main(void)
    {
    
    	int number;
    	int count;
    	int divisor = 2;
    	
    	printf("Input number for primality testing\n");
    	scanf("&#37;d",&number);
    	
    	while (divisor < number/2) {	
    		if (number % divisor == 0) {
    			printf("Number is not prime\n");
    			return 0;
    		}
    		else {
    			divisor++;
    		}
    	}
    
    	printf("Number is prime\n");
    	return 0;
    }
    One isn't prime. And I just always make sure people double check their algorithms against psuedoprime numbers.

  11. #11
    Budding Synth Programmer samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Trefforest
    Posts
    368
    Even better.
    MSVC++ 6.0

  12. #12
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    You really only need to check up to the square root of 'number'. Not all the way up to number/2. And I'd take that bit of math outside of the condition test so that it doesn't get calculated each time. Possibly increment 'divisor' by 2s to cut your execution time in half once more. No need to check with even numbers once you've determined it's not divisible by 2.

  13. #13
    Budding Synth Programmer samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Trefforest
    Posts
    368
    Isn't that the Sieve of Eratosthenes or something?

    A (former) friend of mine thought he discovered that himself and even started writing some wanky 'paper' about it, crowbarring in sine waves for some reason. I quite enjoyed breaking it to him that it was thousands of years old.

    This guy also tried to get me to model AI using a revolving dot. The tool.
    MSVC++ 6.0

  14. #14
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    Close but not quite. The sieve lays out an array of all integers (up to the maximum sought), and then traverses through it - every second element at a time, every 3rd, every 4th, etc, flagging the ones it hit (making them -1 or whatever). The ones that are left when it's all done are primes.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help me with my basic program, nothing I create will run
    By Ravens'sWrath in forum C Programming
    Replies: 31
    Last Post: 05-13-2007, 02:35 AM
  2. Issues with if statement
    By tameeyore in forum C Programming
    Replies: 7
    Last Post: 09-27-2004, 09:34 PM
  3. GetExitCodeProcess ExitProcess Tester..
    By Tony in forum Windows Programming
    Replies: 1
    Last Post: 06-13-2002, 05:02 AM

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