Thread: Conventional?

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2009
    Posts
    16
    Rep Power
    0

    Conventional?


    I have a few quick questions relating to a program I just wrote (very simple, for my own practice only). The first is, is there a way to check the highest value an int can go to, so I can warn the user not to enter that number or more?

    Secondly, if you have a couple of minutes, can you quickly review this short piece of code and let me know if it is "Conventional C", the only other language I've learnt was object orientated so the style was completely different, I'd like to make sure I'm not forcing that onto another language.

    Finally, are there any "mistakes" in this code that don't stop it working, but would cause problems later, or not be the best way to do something.

    Code:
    #include <strings.h>
    #include <stdio.h>
    
    int is_prime(int num);
    
    int main() {
    	int num;
    	int finish;
    	scanf( "%d", &finish);
    	for(num=2;num<=finish;num++){
    		if (is_prime(num)){
    			printf("%d\n",num);
    		}
    	}
    }
    
    
    int is_prime(int num){
    	int divisor;
    	for(divisor=2;divisor<=num/2;divisor++){
    		if (num%divisor==0){
    			return 0;
    		}
    	}
    	return 1;
    }
    Sorry if this is unreasonable in any way.
    Thanks a lot.
    Angus
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2010
    Location
    Grand Rapids-ish, Michigan
    Posts
    142
    Rep Power
    61
    I cannot answer your first question, but the last part i'm curious about:

    Someone correct me if i'm wrong, but shouldn't this:


    Code:
    int is_prime(int num){
    	int divisor;
    	for(divisor=2;divisor<=num/2;divisor++){
    		if (num%divisor==0){
    			return 0;
    		}
    	}
    	return 1;
    }
    be declared as a float instead of an int?

    up at the top he declares it as:

    Code:
    int is_prime(int num);
    shouldn't that be changed to:

    Code:
    float is_prime(int)
    Is that wrong, or is it correct?

    Comments on this post

    • dwise1_aol disagrees : is_prime() returns a "boolean", which in C is an int value of 1 or 0.
  4. #3
  5. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,325
    Rep Power
    2228
    For the range limits of a built-in data type, use the limits.h header file. Consult the macro definitions therein such as INT_MAX, INT_MIN, UINT_MAX, etc.
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2009
    Posts
    16
    Rep Power
    0
    Originally Posted by dwise1_aol
    For the range limits of a built-in data type, use the limits.h header file. Consult the macro definitions therein such as INT_MAX, INT_MIN, UINT_MAX, etc.
    Thanks a lot, any comments on the code or is it fine for my current level?
  8. #5
  9. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2010
    Location
    Grand Rapids-ish, Michigan
    Posts
    142
    Rep Power
    61
    Ok, thanks for sharing that dwise1. I'll remember that. I've not really worked with things like that, and i'm always eager to learn, and that was a good pointer.
  10. #6
  11. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3319
    I can break it with two keystrokes.
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
  12. #7
  13. Hats off to Mr. Joseph donahue
    Devshed Novice (500 - 999 posts)

    Join Date
    Aug 2009
    Posts
    752
    Rep Power
    1111
    1. its int main, but you never returned an integer?
    2. Just in case, in visual studio's the macros are named a bit different, look it up. For example: INT_MAX is _TMP_MAX_S
  14. #8
  15. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2008
    Posts
    222
    Rep Power
    240
    The code got some loopholes like:
    1. Not checking the return value of scanf
    Think about what would happen if the user enters non numeric character for example.
    scanf
    2. Not returning a meaningful value from main,

    but aside from that the algorithm you use can be made more efficient. If it is of any interest to you you can continue reading or just use these wikipedia pages:

    Sieve of Eratosthenes

    Trial Division

    first Lets look at the following somewhat improved primality testing function:

    c Code:
    unsigned isPrime (unsigned n) {
    	if (n == 2)
    		return 1;
    	if (n < 2 || (n % 2 == 0))
    		return 0;
     
    	for (unsigned i = 3; i*i < n; i += 2)
    		if (n % i == 0)
    			return 0;
    	return 1;
    }


    1. If a number is even it's obviously not prime, so we're only have to check the remaining odd numbers for primality, which theoretically cuts the number of tests to half, of course you can argue that we could also exclude all the numbers divided by 3, and by 5 and so on... (which will lead us to the next method which I'm going to show you).

    2. It is sufficient to test all the odd numbers up until the square root of n, because if x is a factor of n then there must be another factor y such that x*y = n, and it's easy to see that x must be smaller than the square root of n.

    The second solution requires additional space in the form of an array the size of the number you want to find prime up to, and it's called the Sieve of Eratosthenes, the wikipedia page provides good explanation of this algorithm.
    Last edited by nebelung; September 2nd, 2010 at 04:24 PM.
  16. #9
  17. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,119
    Rep Power
    1807
    Originally Posted by theburger
    Finally, are there any "mistakes" in this code
    The obvious mistake is the one that means that it does not compile! How did you test this code? Did you really mean <strings.h>?

    As it happens, nothing in your code requires any header other than <stdio.h>. Then it compiles without warnings (VC++ 2008), so that is a good start.

    I personally dislike your indentation style since it does not clearly visually pair-up opening and cloising braces, but that is a personal issue (unless you are coding in a team and need to conform to project defined coding style).

    While on teh subject of style, horizontal and vertical whitespace can be used ot aid readability; don't cram your code, and clearly space your identifiers from your operators.

    Having functions with multiple return statements, or a return aywhere other than the last statement is often frowned upon (I am frowning now). The practice is problematic in large and complex functions and for debugging; for example to break when a function returns, you will have to set multiple break-points in the function (and make sure you set then for all). For example, you can eliminate the multiple return in is_prime() as follows (Nebelung's improvements notwithstanding):

    Code:
    int is_prime( int num )
    {
    	int divisor;
    	for( divisor = 2; divisor <= num / 2 && num % divisor !=0; divisor++)
    	{
    	    // do nothing
    	}
    	
    	return num % divisor != 0;
    }
    If the return value from scanf() (which you failed to test), is not equaly to the number of format specifiers, it has failed to parse the input stream as requested, and the variable finish will have an undefined value (because it was not initialised or assigned); you should not start the loop in this case.

    So long as you realise that this is a very sieve prime algorithm, ok.
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2010
    Posts
    146
    Rep Power
    0
    you can also check the input whit a simple function like this

    Code:
    void get_int(int *number){
    	
    	printf("insert a number: ");
    	while(scanf("%d", number) != 1){
    		printf("invalid input!!!\ninsert a new number: ");
    		while(getchar() != '\n');
    	}
    	
    }
    or

    Code:
    int get_int(void){
         
         int number;
    
         printf("insert a number: ");  
         while(scanf("%d", &number) != 1){
                       printf("invalid input!!!\ninsert anew number: ");
                       while(getchar() != '\n');
         }
       
         return number;
    }
  20. #11
  21. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,782
    Rep Power
    4302
    Originally Posted by nebelung
    first Lets look at the following somewhat improved primality testing function:

    c Code:
    unsigned isPrime (unsigned n) {
    	if (n == 2)
    		return 1;
    	if (n < 2 || (n % 2 == 0))
    		return 0;
     
    	for (unsigned i = 3; i*i < n; i += 2)
    		if (n % i == 0)
    			return 0;
    	return 1;
    }
    One more optimization is in the for loop. The way you have it currently, the compiler has to always do multiplies each time in the for loop, because the terminate condition is i*i < n. Since i is not a constant within the loop, the compiler has to do a multiply each time.

    One way to do this is to check this instead:
    i < ((unsigned) sqrt(n))

    A smart optimizing compiler will note that n stays constant throughout the loop and therefore evaluate sqrt(n) only once in the loop.

    If you have a non-optimizing compiler, you could make sure like this:
    Code:
    unsigned n_max = (unsigned)sqrt(n);
    ...
    	for (unsigned i = 3; i < n_max; i += 2)
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  22. #12
  23. Commie Mutant Traitor
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Jun 2004
    Location
    Alpharetta, GA
    Posts
    1,809
    Rep Power
    1574
    The major advantage of the Sieve of Eratosthenes algorithm is that it can be a lot faster than approaches which actively test each integer; all it really does is step through the multiples of the primes and marks them off. It's major downside is that is takes a large amount of memory, but with a modern 64-bit system with more than 4GB, even this is no hindrance - you can step through the entire 32-bit memory range in a matter of minutes, at least in principle. Since I have an older PC with significantly less memory, I intentionally limited the search space to 'only' the first 10,000,000 integers, which it went through in less than 30 seconds.

    C Code:
    #include <stdio.h>
    #include <string.h>
    #include <time.h> 
    #include <stdbool.h>
     
    const int SPACE_SIZE = 10000000;
    const int COLUMNS = 6;
     
    int main()
    {
        unsigned start, end;
        int prime_count = 0;
        bool digits[SPACE_SIZE];
     
        // set the entire array to a default of 'true'
        memset((void *) digits, 1, SPACE_SIZE);
     
        start = clock();
        for (int i = 2; i < SPACE_SIZE; i++)
        {
            // advance to the next value not yet set as composite
            while (digits[i] == false)
            {
                i++;
            }
     
            if (i > SPACE_SIZE)
                break;        
     
            printf("%8d, ", i);
            prime_count++;
            if ((prime_count % COLUMNS) == 0)
            {
                printf("\n");      
            }
     
            //  step through the multiples of the current prime
            //  and mark them off
            for (int j = i + i; j < SPACE_SIZE; j += i)
            {
                digits[j] = false;
            }
        }
     
        end = clock();
        float time_used = (end - start) / (float) CLOCKS_PER_SEC;
        printf("\n%d primes found in %.2f sec. compute time\n", prime_count, time_used);
     
        return 0;
    }

    Feel free to compare this to your program's performance on your own system.
    Last edited by Schol-R-LEA; September 3rd, 2010 at 02:36 PM. Reason: Added timing and improved formatting to program
    Rev First Speaker Schol-R-LEA;2 JAM LCF ELF KoR KCO BiWM TGIF
    #define KINSEY (rand() % 7) λ Scheme is the Red Pill
    Scheme in Short Understanding the C/C++ Preprocessor
    Taming Python A Highly Opinionated Review of Programming Languages for the Novice, v1.1

    FOR SALE: One ShapeSystem 2300 CMD, extensively modified for human use. Includes s/w for anthro, transgender, sex-appeal enhance, & Gillian Anderson and Jason D. Poit clone forms. Some wear. $4500 obo. tverres@et.ins.gov
  24. #13
  25. Lord of Dorkness
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2004
    Location
    Central New York. Texan via Arizona, out of his element!
    Posts
    8,524
    Rep Power
    3319
    There's an old post on the forum (the OP was GTPC, I believe) that uses bits to mark off the numbers. Reduces memory requirements.

    Comments on this post

    • Schol-R-LEA agrees : Good point.
    Functionality rules and clarity matters; if you can work a little elegance in there, you're stylin'.
    If you can't spell "u", "ur", and "ne1", why would I hire you? 300 baud modem? Forget I mentioned it.
  26. #14
  27. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2009
    Posts
    16
    Rep Power
    0
    As a response to those of you who replied, thank you for your help.

    Regarding the various problems pointed out, I did not think about the scanf checking and returning an integer from main so thanks. I meant to type string.h but I'm not sure why I included this... thanks for pointing that out. Weirdly it compiles fine on my system with gcc. I will try to avoid multiple return statements in future.

    Finally the optimization of the algorithm was not really a concern to me at the time. I intend to make it more advanced but right now I'm just worried about writing valid C code than producing a perfect algorithm. I plan to use a slightly different algorithm to the Sieve of Eratosthenes because it has memory inefficiencies (it stores all the numbers including the non-primes).
    Thanks
    Angus

IMN logo majestic logo threadwatch logo seochat tools logo