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

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?


#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] != '\0'; i++){
            if (!isdigit(argv[j])) {
                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;
 
}

Reply 1

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.

Reply 2

Dr Jake

Original post by DFranklin

You make a fair point. Can you suggest a simple way of optimising my sieve?


int i, j, primeArray[n];

for (i = n; i--; ) 
    primeArray = 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);

Reply 3

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.

Reply 4

Dr Jake

Original post by DFranklin

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?

Reply 5

DFranklin

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.

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

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you