Thread: Prime number calculator, can't seem to find bug?

  1. #1
    Registered User
    Join Date
    Mar 2018
    Posts
    5

    Prime number calculator, can't seem to find bug?

    Hi everyone, I am trying to practice C. I wrote a prime-or-composite calculator, but my output always ends up suggesting the number is prime, when in fact it should be composite. I've looked over my code numerous times and I've compared it to others and I still don't see what I am doing wrong. If someone else could look at my code and inform me as to what is wrong with my code that would be great - a second pair of eyes always help. By the way, I know I don't have to utilize pointers to accomplish this program, but I'm just trying to get some practice with them.

    Here is my code:

    Code:
    #include <stdio.h>
    
    int main()
    {
        int num, *pnum;
        int i, flag = 0;
        
        pnum = &num;
        
        printf("\nEnter any number: ");
        scanf("%d", pnum);
        
        while (*pnum != -1)
        {
            if (*pnum == 0 || *pnum == 1) {
                printf("\n\t%d is neither prime nor composite", *pnum);
            } else if (*pnum == 2) {
                printf("\n\t%d is prime", *pnum);
            } else {
                for (i = 2; i < ((*pnum) / 2); i++ ) 
                {
                    if (*pnum % i == 0)
                        flag = 1;
                        break;
                }
                
                if (flag == 0) {
                    printf("\n\t%d is prime", *pnum);
                } else {
                    printf("\n\t%d is composite", *pnum);
                }
            }
            
            flag = 0;
            printf("\n\nEnter any number: ");
            scanf("%d", pnum);
            
        }
        
        return 0;
    }

    output:

    Enter any number: 0

    0 is neither prime nor composite

    Enter any number: 1

    1 is neither prime nor composite

    Enter any number: 2

    2 is prime

    Enter any number: 3

    3 is prime

    Enter any number: 4

    4 is prime

    Enter any number:

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    It says 4 is prime because your for loop only goes as long as i is LESS THAN half the number, so it never tests 4 with the divisor 2. The condition needs to be <=. But actually, you only need to test up to the square root, which is a lot less than half for bigger numbers.

    And if you test for divisibility by 2 separately then you can speed up the loop by only testing odd numbers.
    Code:
        int is_prime = 1;
        if (num % 2 == 0)
            is_prime = (num == 2);
        else {
            for (int i = 3; i * i <= num; i += 2)
                if (num % i == 0) {
                    is_prime = 0;
                    break;
                }
        }
        printf("\t%d is %s\n", num, is_prime ? "prime" : "composite");
    Last edited by john.c; 03-13-2018 at 05:40 PM.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  3. #3
    Registered User
    Join Date
    Mar 2018
    Posts
    5

    Thumbs up

    Quote Originally Posted by john.c View Post
    It says 4 is prime because your for loop only goes as long as i is LESS THAN half the number, so it never tests 4 with the divisor 2. The condition needs to be <=. But actually, you only need to test up to the square root, which is a lot less than half for bigger numbers.

    And if you test for divisibility by 2 separately then you can speed up the loop by only testing odd numbers.
    Code:
        int is_prime = 1;
        if (num % 2 == 0)
            is_prime = (num == 2);
        else {
            for (int i = 3; i * i <= num; i += 2)
                if (num % i == 0) {
                    is_prime = 0;
                    break;
                }
        }
        printf("\t%d is %s\n", num, is_prime ? "prime" : "composite");
    Thanks John, appreciate it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help to find prime factors of a number
    By san12345 in forum C Programming
    Replies: 2
    Last Post: 12-15-2015, 11:50 PM
  2. Find Prime Factors Of Given NUmber
    By san12345 in forum C Programming
    Replies: 2
    Last Post: 12-03-2015, 02:35 AM
  3. Replies: 1
    Last Post: 05-27-2010, 12:57 PM
  4. help, trying to find prime number
    By vampirekid.13 in forum C++ Programming
    Replies: 19
    Last Post: 05-02-2009, 03:29 PM
  5. Find first 250 Prime Number
    By dummies in forum C Programming
    Replies: 4
    Last Post: 01-12-2007, 09:18 AM

Tags for this Thread