Prime factors of a number in C

Question

The following is code on "prime factors of a number". Any suggestions to optimize the code? It runs for a pretty long time for inputs like 35068499. I also want the code to take 10 digit numbers as input.

#include<stdio.h>
void pf(long);
void main()
{
    printf("Enter a number: ");
    scanf("%ld",&n);
    pf(n);
}
void pf(long n)
{
    long i,x;
    while(n%2==0)
    {
        printf("2\n");
        n=n/2;
    }
    x=3;
    while(x<=n)
    {
        for(i=2;i<x;i++)
        {
            if(x%i==0)
            {
                goto abc;
            }
        }
        while(n%x==0)
        {
            printf("%ld\n",x);
            n=n/x;
        }
        abc:
            x=x+2;
    }
}

Answer 1

Can you describe a bit your algorithm ? There is no comments in your code and it is not straightforward (because no comments is acceptable when the code is easy to read, but not in this case). A few things that you should consider :

• the use of global variables is here totally inapropriate, n should not be global and your function pf should take an argument (and should also return an array of the prime factors found, if you need them)
• the while(1) is useless the two times you used it. It is commonly bad practise to use this, and especially when there is only one condition in the loop and when you exit the loop when the condition is not true. You should use while(condition) instead
• Name correctly your variables ! What are i, x, n ? It improvs readability by a lot with absolutely no cost, so you should do it
• I also don't see why you need the goto. Again it makes your code hard to read for no obvious good reason.
• If n is a positive number, you should use an unsigned type. Since you want to be able to process 10 digits numbers, I would recommend using unsigned long long

Aside from that, I think it's mostly the algorithm that you use that is ineffective, which is why you should explain what you tried to do.

Answer 2

If I follow the purpose of the for-loop correctly, you are trying to determine if 'x' is a prime number. This, I suspect is the major reason it is running for a pretty long time for inputs like 35068499. Pending further analysis, I don't think that this for-loop is needed.

Consider what happens in the following loop:

while (n%x == 0) {
    printf (...);
    n = n/x;
}

If 'x' is a prime, 'n' has a chance of being evenly divisible by 'x'. If 'x' is not a prime, then it must by definition by a product of two or more primes. However, you have already identified all those primes. Thus at every iteration of the second while-loop, the only values that can possibly divide evenly into 'n' are prime. Eliminate the for-loop (and 'abc' label) and save yourself some computation time.