Thread: how to cleanup prime numbers program?

  1. #1
    Registered User
    Join Date
    Aug 2014
    Posts
    11

    how to cleanup prime numbers program?

    I got my prime numbers software to work. It first gets a max (so there is no annoying infinite loop), then enters for loop 'i' (which is the number to be tested). For loop 'j' is where is counts up to the current number/'i', checking is there is a '%'/remainder of 0 (after first ignoring every even number). The problem I had was how to both escape the counting/'j' loop, and be able to report a printf to console for the number being found as a prime number. Right now, I have an int 'isPrime' that will either be '1' or '0' (my quick emulation of bools). That entire sections seams like it is excessive, and would like to know how I can condense it- or make it 'smarter'. (yes my method for finding prime number may not be the best, but that is ok)

    Code:
    #include<stdio.h>
    
    int main (){
        
        int max, remainder, i, j, isPrime;
        printf("Please provide a maximum number: ");
        scanf("%d", &max);
        printf("\nThank You!\n\n");
        for (i = 2; i <= max; i++){
            if ((i%2) != 0){
                for (j = 2; j < i; j++){
                    remainder = i % j;
                    //printf("J : %d | I: %d | R : %d \n",j,i,remainder); //Emergency Line for Reading Information
                    if (remainder == 0){
                        isPrime = 0;
                        break;
                    } else {
                        isPrime = 1;
                    }
                }
                if (isPrime == 1){
                    printf("%d \n", i);
                }
            }
        }
        printf("Done!");
        return 0;
    }

  2. #2
    Registered User
    Join Date
    Jun 2015
    Posts
    1,643
    Handle 2 separately.
    Start your loops at 3 and increment by 2.
    End your inner loop at the square root of i.
    Do away with the flag and just test the loop variable to see why the loop terminated.

    Putting this together:
    Code:
    #include <stdio.h>
    #include <math.h>
    
    int main(void) {
        int max, n, d;
    
        printf("Enter the maximum: ");
        scanf("%d", &max);
    
        if (max > 1) printf("2 ");
        
        for (n = 3; n <= max; n += 2) {
            int sq = (int)sqrt(n);
            for (d = 3; d <= sq; d += 2)
                if (n % d == 0)
                    break;
            if (d > sq)
                printf("%d ", n);
        }
    
        printf("\n");
        return 0;
    }

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,161
    Instead of a variable named isPrime, I would suggest a function:
    Code:
    int isPrime(int i){
        int j;
        if ((i%2) != 0){
            for (j = 2; j < i; j++){
                if (i % j == 0){
                    return 0;
                }
            }
            return 1;
        }
        return 0;
    }
    Your loop in the main function can then be simplified to:
    Code:
    for (i = 2; i <= max; i++){
        if (isPrime(i)){
            printf("%d \n", i);
        }
    }
    Note that your program has a bug: it does not list 2 as a prime number. I have left the bug in place for you to fix.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 3
    Last Post: 12-02-2014, 10:11 AM
  2. C program for prime numbers
    By arslan20 in forum C Programming
    Replies: 21
    Last Post: 05-19-2013, 04:42 PM
  3. Replies: 1
    Last Post: 03-16-2012, 02:07 AM
  4. non prime numbers or composite numbers program.help plz!
    By danishzaidi in forum C Programming
    Replies: 10
    Last Post: 11-15-2011, 11:10 AM
  5. C Program for Prime Numbers
    By mmuhlenb in forum C Programming
    Replies: 12
    Last Post: 02-19-2003, 04:55 AM

Tags for this Thread