Hey there! Sign in to join this conversationNew here? Join for free

C code for taking 2 command line inputs and verifying that they are integers Watch

    • Thread Starter
    Offline

    6
    ReputationRep:
    I'm taking 2 command line inputs, which have to be integers between 2 and 1,000,000. These two values are then passed into the getPrimes function, which is just a Sieve of Eratosthenes algorithm, printing all prime numbers within the range specified by the two inputs. The two inputs, n and k, must be positive integers, where n > k. How can I better optimise my approach to collecting these inputs and verifying them, to decrease execution time?

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #include <ctype.h>
    #define MAXVALUE 1000000 
     
    int main(int argc, char *argv[]){
    
        if (argc != 3){
            printf("Warning: Check number of arguments.\n";);
            return 1;
        }
    
        int i, j;
        for (j = 1; j <= 2; j++){
            for (i = 0; argv[j][i] != '\0'; i++){
                if (!isdigit(argv[j][i])) {
                    printf("Warning: Please enter a valid integer.\n";);
                    return 1;
                }
            }
        }
    
        char *endptr;
        int n = strtol(argv[2], &endptr, 10), k = strtol(argv[1], &endptr, 10); //convert argv to int
    
        if (n > MAXVALUE || k == 1 || k >= n){
            printf("Warning: Bad input.\n";);
            return 1;
        }
    
        getPrimes(n, k);
    
        return 0;
     
    }
    Offline

    17
    ReputationRep:
    Huh? Verifying the inputs are integers is going to take less than a microsecond. Given the amount of work involved in sieving a million integers, you're looking for performance savings in the wrong place.
    • Thread Starter
    Offline

    6
    ReputationRep:
    (Original post by DFranklin)
    Huh? Verifying the inputs are integers is going to take less than a microsecond. Given the amount of work involved in sieving a million integers, you're looking for performance savings in the wrong place.
    You make a fair point. Can you suggest a simple way of optimising my sieve?

    Code:
    int i, j, primeArray[n];
    
    for (i = n; i--; ) 
        primeArray[i] = 1;
    
    for (i = 2; i * i < n; i++)
        for (j = i * i; j < n; j += i)
            primeArray[j] = 0; 
    
    for (k = k; k < n; k++) 
        if (primeArray[k] == 1) 
            printf("%d\n", k);
    Offline

    17
    ReputationRep:
    First thing I'd do is time your code with and without the printf. Chances are, you're spending most of your time here and (unless you're happy to not print the primes) there's not a lot you can do about it.

    Things you can do to speed up the actual sieving:

    There's no need to do the "remove multiples" phase (the j loop) unless i is prime.

    Making primeArray be an array of chars will make better use of cache.

    The other standard thing is to treat 2 as a special case and then work exclusively with odd numbers (so the kth entry in the array represents the kth odd number). This needs a bit more effort to get right than the first two suggestions.
    • Thread Starter
    Offline

    6
    ReputationRep:
    (Original post by DFranklin)
    First thing I'd do is time your code with and without the printf. Chances are, you're spending most of your time here and (unless you're happy to not print the primes) there's not a lot you can do about it.

    Things you can do to speed up the actual sieving:

    There's no need to do the "remove multiples" phase (the j loop) unless i is prime.

    Making primeArray be an array of chars will make better use of cache.

    The other standard thing is to treat 2 as a special case and then work exclusively with odd numbers (so the kth entry in the array represents the kth odd number). This needs a bit more effort to get right than the first two suggestions.
    Thanks, I've implemented your first two suggestions and the execution time has gone down a bit. Can you offer any hints as to how to get started with your third suggestion?
    Offline

    17
    ReputationRep:
    To get to grips with the 3rd suggestion, I would use pen+paper to get an idea of how you might do it. You'll need to keep translating between position in the array (i.e. the kth odd number) with the actual number it corresponds to.

    So, for example, you find that the 2nd odd number is prime. This corresponds to 3. You now want to remove odd multiples of 3. That is, 9, 15, 21, etc.
    Note that 9 is the 5th odd number, 15 is the 8th odd number, 21 is the 11th odd number and so on. So you need to zero the 5th, 8th,11th and so on elements of the array.
    Then go on to finding the next odd prime that you need to sieve, and so on.

    However, I very quickly hacked up a sieve on my laptop (not using the 3rd suggestion), and it takes approximately 0.1 seconds to sieve all the numbers from 1 to 1000000 (and about 20 seconds to print them). So I'm not sure it's worth expending more effort at this point.
 
 
 
Reply
Submit reply
TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

Updated: November 10, 2017
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    What newspaper do you read/prefer?
    Useful resources
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.