C prime factorization (loop failure?)

Question

I've been looking into this simple piece of code for 1.5 hrs now and do not find the mistake. I start going crazy ;)

Could anyone of you with a fresh mind and view give me a little hint, where I might have the mistake in? (I am relatively new to C)

The problem is: The code works fine for most of the numbers I entered and tested, but accidentically I found a number that does not work: 3486118 (or 55777888 which is a multiple of it) It goes right for the first loop(s), but after factor 2 it becomes an endless loop.

Here is my code: (any help is greatly appreciated)

// Program calculates prime factors of entered number and returns them

#include <stdio.h>

int main() {

    long int num, num_cp;
    long int product=1;

    /*prime number array up to 100.000*/
    long int prime[] = {2, 3, **[...cut out MANY numbers...]** 99971, 99989, 99991};

    printf("Please enter a positive integer:\n");
    scanf("%li", &num);//55777888 or 3486118 not working... why?
    //copy the entered number to keep the original for comparison with "product" and "break;" if equal
    num_cp=num;

    printf("prime factorization of %li:\n\n", num);

    for (int i=0; i<sizeof(prime); i++) {
        if (num_cp%prime[i]==0) {
            num_cp/=prime[i];
            product*=prime[i];
            if (product==num) {
                printf("%li\n\n", prime[i]);
                break;
            }
            printf("%li*", prime[i]);

            //If prime factor found but "product" is still not equal to "num" reset loop counter "i" to -1 (==0 in next loop)
            i=-1;
        }
    }
    printf("END");
    return 0;
}

Answer 1

The prime factors of 55777888 are 2·2·2·2·2·1743059, where the last factor is too large to be contained in your list.

You can fix this in your code: When the product is equal to the product of the prime factors you have found, num_cp is 1. If num_cp is greater than one after you have exhausted your prime list, it is a factor of num. If num/num_cp is smaller than the largest prime you have checked, you can assume that the remaining value of num_cp is a prime. If it wasn't you'd have found more factors earlier.

You can fix this by adding an additional check after your main loop:

if (num_cp > 1) printf("%li\n\n", num_cp);

(If long int is a 64-bit number on your system, you're still not safe: The remaining factor might be made up of several numbers that are not in your array.)

Finally: Resetting the for loop counter so that the loop starts over isn't a good idea. It always starts from the beginning and re-checks primes that you have already checked. And it just isn't natural program flow, which makes it hard to read. A while loop instead of the inner if block would be more natural in my opinion.

Edit: To illustrate:

#include <stdio.h>

int main() {
    long int num;

    /* prime number array up to 100.000 */
    long int prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
    int nprime = sizeof(prime) / sizeof(*prime);

    num = 55;

    printf("%li == ", num);

    for (int i = 0; i < nprime; i++) {
        long int p = prime[i];

        if (num <= 1) break;

        while (num % p == 0) {
            num /= prime[i];
            printf("%li", p);
            if (num > 1) printf(" * ");
        }
    }

    if (num > 1) printf("%li", num);
    printf("\n");

    return 0;
}

Things to note:

• Instead of resetting the main loop counter i, a while loop is used, which consumes all repetitions of the same factor. If a prime p doesn't divide the number, the while loop isn't entered, just like an if clause.
• I've removed the copy of num and used num throughout, mainly to remove clutter. I've also removed the product. Your logic that all prime factors should multiply to the original number, is good. But it also works the other way round: After dividing the number by all primes, we are left with 1. And we have to divide the number anyways. By removing the product, we have to keep track of only one variable instead of two.
• I've moved the break condition to the front, so we catch negative numbers and 0 early.

That said, your way to code isn't wrong, just maybe a bit unusual in places.

Answer 2

"I've been looking into this simple piece of code for 1.5 hrs now and do not find the mistake. I start going crazy ;)"

Don't. Leave it. Go away and eat a pizza. Veg out in front of your favourite movie. Have a shower. Aim for a new high-score on 2048 (or whatever). Your brain gets stuck in a rut and you are no longer seeing your code. You are only seeing what you think your code is.

When you get your brain out of the rut, then -- and only then -- go back and actually read the code you wrote. Not the code you think you wrote, but the code you actually wrote. Yes, they are different.