John and Bijan already reviewed your algorithm then let me go with the boring part of reviewing your C code.
In modern C you do not need to declare all variables at the beginning of the function; do it as late as possible, give them a meaningful name and initialize them only if required (not in this case). Assuming C99:
printf("Insert first and last number (separated by space): ");
int firstNumber, lastNumber;
scanf("%d %d", &firstNumber ,&lastNumber);
int megaPrimeCount = 0;
for(int number=firstNumber; number <= lastNumber; ++i) {
...
}
I admit that number instead of i is little bit pedantic in this case but it is to give the idea. Also you're not checking your inputs, it may be an issue or not but it's as simple as:
if (firstNumber < 1 || firstNumber > lastNumber) {
printf("1 <= first <= last <= 10^15\n");
return 1;
}
You may want also to move inputting into a separate function like readRange().
Inside your loop the code can be simplified because:
- You do not need to check
!= 0 for (i % 2) because integer to boolean conversion is automatic. You may also want to introduce a separate function for that.
- No need to return
int from isMegaPrime(), C99 introduced _Bool type and you may include stdbool.h to use a convenient bool macro.
- There is not any performance penalty to use prefix or postfix increment but I can't stop myself to double-check the reason there is the postfix every time I see it then...
In code:
if (isOdd(number) && isMegaPrime(number))
++megaPrimeCount;
However...why do you put the the optimization to skip even numbers inside this function? You shouldn't span knowledge here and there randomly, this function is already doing too much (reading inputs, counting mega prime numbers and outputting that number):
if (isMegaPrime(number))
++megaPrimeCount;
isMegaPrime() can be greatly simplified (note that here I keep exactly your original algorithm, I'm review just coding style). Few things to note:
- Reduce indentation,
else condition of a return does not need to be.
- You do not need
flag, just return whenever appropriate.
- Use
bool instead of int where appropriate.
- Be consistent with spaces and formatting.
- Use appropriate names, context and variable name will help you to understand the algorithm. For example
temp doesn't help me that much to understand what the function is doing, there is no reason to avoid writing if (!isPrime(number % 10)) but introducing an extra variable (that will be optimized away by the compiler!) will help reader to understand the code.
In code:
bool isMegaPrime(int number) {
if (!isPrime(number))
return false;
while (number != 0) {
int digit = number % 10;
if (!isPrime(digit))
return false;
n /= 10;
}
return true;
}
That while loop hurts me little bit and I'm tempted to change it to see how it will look like with a for (also stopping to overwrite parameter value) but let it be...
isPrime() can have the same treatment we reserved to isMegaPrime():
bool isPrime(int number)
{
if (number == 1 || isEven(number))
return false;
int upperLimit = (int)sqrt(number);
for (int divisor = 2; divisor <= upperLimit; ++divisor) {
if (number % divisor == 0)
return false;
}
return true;
}
Now I see that we're always using isPrime() return value negated. I dislike negations because sometimes I do not see them (age?) then I'd rewrite it to be isNotPrime() simplifying both functions (of couse if isPrime() isn't used anywhere else).
As exercise you may also want to add some assertions to your code to enforce the constraints you have. Not such useful in this small snippet but good habit for bigger code bases.
It may not be the case for this code but as you can see, for example in Python, generators like range() are pretty handy and nice. You may enjoy to experiment reading Generators in C. Imagine to write your code like this:
FOR(number, range, firstNumber, lastNumber) {
...
}
And:
FOR(divisor, range, 2, (int)sqrt(number)) {
...
}
You may find it interesting (if not here then in other applications).
