Project Euler Problem #51 in C

Question

Here is the problem statement for problem #51:

By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

I'm learning C right now, and this solution is my first original program in the language. I'd love any feedback on it, whether its about style, the algorithm, or any language tricks I could have used to save some time(especially if pointers could have come in handy somewhere. I'm coming from Python, and I feel like I'm stuck in that perspective when it comes to types and variables). It's not the most concise thing in the world, but it gets the right answer in about 2 minutes on my machine. Thanks in advance!

#include <stdio.h>
#include <math.h>

int isprime(int num);
long quick_pow10(int power);

/*solve Project Euler problem 51*/
int main() 
{
    /*length of potential answer(including last digit)*/
    int l = 3; 
    long ans = -1;
    /*in binary, which digits we should change(not including 
     * last digit)*/
    unsigned int digs;

    /*loop through lengths of test numbers while ans hasn't been found*/
    while(ans < 0) {
        printf("l = %d\n", l);
        /*loop across which digits to replace(last digit is never
         * replaced because it must be odd)*/
        for(digs=1; (digs<(1 << (l-1))) && (ans < 0); digs++) {
            /*digs, but including last digit*/
            unsigned int reps = digs << 1;
            printf("    reps=%u\n", reps);
            int onecount = 0;
            int ones[l];
            int i;
            int bit;
            /* value of digits that aren't changed */
            long g;
            /*count how many digits are going to be changed and record
             * which*/
            for(i=l - 1; i >= 0; i -= 1) {
                bit = (reps >> i) & 1;
                if(bit == 1) {
                    ones[onecount++] = l - 1 - i;
                }
            }
            /*loop through the possible cumulative values for the 
             * non-replaced digits in the test number*/
            for(g = quick_pow10(l-1-onecount) + ((l-1-onecount)>0);
               (g < quick_pow10(l-onecount)) && (ans < 0);
                g+=2) {
                /* test the l-digit number testnum with the
                * substitutions at digits listed in 'ones.' 
                * non substituted digits are in g.*/
                int t;
                int primecount = 0;
                int failcount = 0;
                /*digit counter in g, from least significant*/
                int gdc = 0;
                /*location in testnum, from least significant digit*/
                int tni;
                long testnum = 0;
                long testnumt;

                /*put gdigits into correct locations in testnum*/
                for(tni=0; tni < l; tni++) {
                    if(!((reps >> tni) & 1)) {
                        testnum += 
                        ((g / quick_pow10(gdc++)) % 10) * 
                        quick_pow10(tni);
                    }
                }

                /*loop across the members of the family of 
                 * substitutions. Include 0 only if the first digit 
                 * isn't being changed*/
                for(t=9; t >= (int)((reps >> (l - 1)) & 1); t--) {
                    testnumt = testnum;
                    int k;
                    /*build the final testnum*/
                    for(k=0; k < onecount; k++){
                        testnumt += t * quick_pow10(l - 1 - ones[k]);
                    }

                    if(isprime(testnumt)) {
                        primecount += 1;
                    } 
                    else {
                        if((++failcount) >= 3) {
                            break;
                        }
                    }
                }

                if(primecount >= 8) {
                    ans = testnumt;
                } 
            }
        }
        l++;
    }
    printf("%ld\n", ans);
}


long quick_pow10(int power)
{
    static long pow10[11] = {
        1, 10, 100, 1000, 10000, 
        100000, 1000000, 10000000, 100000000, 1000000000, 10000000000
    };

    return pow10[power];
}


int isprime(int num)
{
     if (num <= 1) return 0;
     if (num % 2 == 0 && num > 2) return 0;
     for(int i = 3; i < num / 2; i+= 2)
     {
         if (num % i == 0)
             return 0;
     }
     return 1;
}

EDIT: I was looking at the forum(that opens up when you post a solution) and it turns out that everyone was getting much faster speeds than me by looping across the primes instead of all natural numbers. I'm not changing my code, but in case you're interested :.

Answer 1

Variable names

Right off the bat, l is a terrible name. Not just because it's short and requires me to scroll up to see what it's for, but also because it looks very similar to 1 which on certain editors is bound to confuse readers. In general, variables should be self-descriptive and not require a comment to explain its purpose.

Comments

Your existing comments don't make the code easier to read and the places in your code which are cryptic don't have explanations. In general, it's useful to:

• Have a long comment before the method explaining the purpose of the function, the algorithm/how it works, the parameters (not just to the function, but also to the algorithm), expected input/outputs, etc.

• Inline comments (i.e //) that explain cryptic parts of code, although this is just a bandage to hard to read code.

For example:

            /*put gdigits into correct locations in testnum*/
            for(tni=0; tni < l; tni++) {
                if(!((reps >> tni) & 1)) {
                    testnum += 
                    ((g / quick_pow10(gdc++)) % 10) * 
                    quick_pow10(tni);
                }
            }

is a rather useless comment since all it says is that you're putting something into another thing without actually explaining the algorithm.

Declare variables right before you use it

In many cases you are declaring loop index variables far removed from where you're using them and there's no indication what they're loop index variables. The code becomes much harder to reason about because the reader has to keep all of this information in their head and it's difficult to tell if the variable may be changed between when it's declared and used.

In C99, you can even declare the variable inside the loop:

for (int i = 0; i < 10; ++i) {
}

isprime loop condition

Why n / 2? As far as I'm aware, the typical terminating condition is sqrt(n).

Unsigned/signed comparison

In this comparison:

    for(digs=1; (digs<(1 << (l-1))) && (ans < 0); digs++) {

You are comparing an unsigned/signed expression. The signed value will be converted to unsigned and the comparison may have unwanted semantics.

Answer 2

Overall, a good initial post.

1. Avoid a big main() wall of code. Break it down into chunks of logic like the following. Of course Euler51() will be the biggest helper function, yet that will form a nice function for later coding tasks. Even Euler51() should be broken down into sub-functions.

    Initialization;
    GetUserInput(&Number, &Mask);
    unsigned answer = Euler51(Number, Mask); 
    DisplayAnswer(answer);
   

2. For unsigned problems, consider using unsigned types. I see no need for unsigned math here and IMO, using unsigned types would simplify code. For learners, pay special notice of decrementing 0 and making sure various constants are unsigned.

3. Mathematically, only need to test candidate divisors up to the square root of num. Avoid the FP function double sqrt(double x) as 1) the result may be slightly less than expected and the conversion to an integer suffers truncation 2) double often lacks the precision of wide integer types which invites errant functionality. 3) Often not needed as modern processors typically compute the quotient and remainder at the same time allowing the quotient to be used as the exit condition an no extra computation cost.

    bool isprime(unsigned num) {
      if (num % 2 == 0) return num == 2;
      unsigned quotient = num - 1;
      for (unsigned divisor = 3; divisor <= quotient; divisor += 2) {
        if (num % divisor == 0) return false;
        quotient = num / divisor;
      }
      return num > 1;
    }
   

4. For the next step in prime number improvements use the Sieve of Eratosthenes.

5. 10000000000 may exceed long range which may be as small as 32-bit. Code may need long long.

6. Avoid manually formating. Below code and other indicate a hand effort.

    // manual
    static long pow10[11] = {
        1, 10, 100, 1000, 10000, 
        100000, 1000000, 10000000, 100000000, 1000000000, 10000000000
    };
   
    // auto 
    static long pow10[11] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
        100000000, 1000000000, 10000000000};
   

7. Was the zero count correct in the constants? Easy to mess up. Could use *. Be sure the lead constant is the width of the target type.

    static long pow10[11] = {1, 10, 100, // 
      1000L, 10L*1000, 100L*1000,  // 
      1000L*1000, 10L*1000*1000, 100L*1000*1000, // 
      1000L*1000*1000, 10L*1000*1000*1000};
   

8. Nice that posted code respected the site presentation width. Code did not need a horizontal scroll bar.

Maybe I will go deeper into OP's logic later - TTFN