You are Here: Home

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

1. 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){
return 1;
}

getPrimes(n, k);

return 0;

}```
2. 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.
3. (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);```
4. 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.
5. (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?
6. 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.

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.

This forum is supported by:
Updated: November 10, 2017
Today on TSR

### Results day under a month away

How are you feeling?

Poll
Useful resources