Find numbers between 1 and 10000 whose sum of digits are prime

Question

I have the following C code that finds numbers between 1 and 10000 whose sum of digits are prime and save then to a file.

#include<stdio.h>
#include<conio.h>
int sum_of_digits(int);
int check_prime(int);
void save_to_file(int);

int main()
{
    int i, num, isPrime;
    for(i=2; i<=10000; i++)
    {
        num = sum_of_digits(i);
        isPrime = check_prime(num);
        if(isPrime)
        {
            printf("%d ", i);
            save_to_file(i);
        }
    }
    getch();
    return 0;
}

int sum_of_digits(int num)
{
    int sum = 0;
    while (num != 0)
    {
        sum += num % 10;
        num /= 10;
    }
    return sum;
}

int check_prime(int num)
{
    int i;
    for (i=2; i<=num-1; i++)
    {
        if (num%i == 0)
            return 0;
    }
    if (i == num)
        return 1;
}

void save_to_file(int num)
{
    FILE *fp;
    fp=fopen("prime.txt","a+");
    fprintf(fp, "%d ", num);
    fclose(fp);
}

Answer 1

The sum of the digits is such a small number (9+9+9+9=36 the maximum in your case) that you can even hard-code the values which are prime or not:

//number:         1  2  3  4  5  6  7
char isPrime[] = {0, 1, 1, 0, 1, 0, 1, ...}

But lets assume you don't go that far. The next best thing would be to generate such an array at run-time before your main loop (also based on the fact that the largest number you need to check if it's a prime is very small). A popular method for doing this is the Sieve of Eratosthenes.

Thus, you can now look up if the sum of the various digits is a prime or not in constant time:

if (isPrime[sum_of_digits(i)])
{
    //...
}

As to writing the results to a file, I would keep the file open for the duration of the loop. This improves efficiency by sending bigger chunks of data to the disk thanks to buffering.

Answer 2

No return path.

Example, with check_prime(1), no value is returned leading to undefined behavior.

int check_prime(int num) {
    int i;
    for (i=2; i<=num-1; i++) {
        if (num%i == 0)
            return 0;
    }
    if (i == num)
        return 1;

    // missing return
    return 0; // recommended

}

Per the code use of check_prime(), such an event is not expected to happen. Yet functions, unless static and heavily documented to detail their limited range, should be more robust. Also, unusual optimizations have been known to occur when code has a path that leads to UB.

Any num < 2 value has trouble. num==INT_MIN leads to another undefined behavior with num-1.

Consider making functions like check_prime(int num) to have some defined behavior over all the range of INT_MIN <= num <= INT_MIN or document its limitations.

int check_prime_suggested(int num) {
    int i;
    for (i=2; i < num; i++) {  // avoid num-1 which may overflow
        if (num%i == 0)
            return 0;
    }
    return i == num;
}

In a similar line-of-thought, int sum_of_digits(int num) has negative results when num < 0. Document the limitations of the intended use of the code or make it so code is well defined and correct functionality for all input values.

Better to check the results of fopen() before using. Use assert() or better yet, add test code.

#include <assert.h>

void save_to_file(int num) {
  FILE *fp;
  fp=fopen("prime.txt","a+"); 
  assert(fp);

Use entire range of task. We know 1 does not pass the test, well neither does 10000 and 9999. Should we code [2 to 9998]? The point is the contract was for numbers [1...10000] and code should clearly demonstrate that:

// for(i=2; i<=10000; i++)
for(i=1; i<=10000; i++)