C finding out prime factor of large number

Question

I wrote the following C code to find out the largest primer factor of a large number and my program when run keeps executing forever.I tried to debug it by assigning iBigNum withing range of 2^32-1,then it worked.

LONG64 iBigNum = 600851475143,iCurr=0,iLarge=0;
    //600851475143 
    /*4294967295
      4000000000
    */iCurr = iBigNum-1;
    while(iCurr > 0 )
    {
        if(iBigNum % iCurr == 0){
            iLarge=iCurr;
            break;
        }
        iCurr--;
    }
    MsgPrintf(TEXT("CustomPrint"),TEXT("%d"),iLarge);

Between,LONG64 is defined as basetsd.h

//
// The following types are guaranteed to be signed and 64 bits wide.
//

typedef __int64 LONG64, *PLONG64;

I am running the code on Intel Core 2 Duo CPU running at 3.16GHz with 4 GB RAM.Is this expected behavior?Can somebody point me some direction? Thank you

Answer 1

It might seem like a good idea to start from the top, because you need to find the biggest factor, but it is not. The smallest possible factor is 2, therefore the greatest possible factor would be n/2. You spend the first n/2, i.e. 300425737571 iterations in vain. It's worse in your case, because the smallest factor is 17.

Don't try to be clever. Start your factorisation from the bottom. When you find a factor, divide your number by it, possibly several times, and store the last factor. Stop when your number is 1.

(This naive method is still bad if your number is, say, the square of a prime, but on average and if you just check one number, it should be reasonably fast.)

Edit: Here's the code that will find the greatest factor in the way I've described above. It will work reasonably fast fon non-primes, but running it on a large prime (479001599) takes about 4 seconds on my machine. The OP's original input was more than 1,000 times as big.

With this caveat out of the way, here goes:

LONG64 max_fact(LONG64 iBigNum)
{
    LONG64 maxFact = 1;
    LONG64 i = 2;

    while(iBigNum > 1)
    {
        while (iBigNum % i == 0){
            iBigNum /= i;
            maxFact = i;
        }
        if (i == 2) i = 3; else i += 2;
    }

    return maxFact;
}

Answer 2

Your algorithm is very slow. This is why it seems to run forever.

• You decrement only 1 at a time. 2 would be more logical (check only odd divisors)
• You do trial division from the top. The first iBigNum/2 you will spend doing nothing as there can be no factor there.

I would suggest you try implementing an actual factorisation algorithm. Pollards-Rho is very simple to implement and will factorise a 64-bit integer in a fraction of a millisecond.

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

static inline intmax_t pollards_rho_randomiser(intmax_t x, intmax_t n) {
    return ((x * x) - 1) % n;
}

static inline intmax_t gcd(intmax_t x, intmax_t y) {
    while (y) {
        intmax_t temp = y;
        y = x % y;
        x = temp;
    }
    return x;
}

intmax_t pollards_rho(intmax_t n) {
    intmax_t x = 2, y = 2, d = 1;

    while (d == 1) {
        x = pollards_rho_randomiser(x,n);
        y = pollards_rho_randomiser(y,n);
        y = pollards_rho_randomiser(y,n);
        d = gcd(abs(x-y), n);
    }

    if (d == n)
        return 0;
    else
        return d;
}

size_t factorise(intmax_t * factors, intmax_t iBigNum) {
    size_t num_factors = 0;

    intmax_t factor;
    while ((factor = pollards_rho(iBigNum))) {
        // makes sure to split everything into primes
        num_factors += factorise(factors + num_factors, factor);
        iBigNum /= factor;
    }

    factors[num_factors++] = iBigNum;

    return num_factors;
}

int compare(const void * a, const void * b) {
    return *(intmax_t *)b - *(intmax_t *)a;
}

int main () {
    intmax_t iBigNum = 600851475143;

    intmax_t factors[200];
    size_t num_factors = factorise(factors, iBigNum);

    qsort(factors, num_factors, sizeof(*factors), compare);
    printf("%" PRIiMAX " = %" PRIiMAX, iBigNum, factors[0]);

    size_t i;
    for (i = 1; i < num_factors; i ++) {
        printf("* %" PRIiMAX, factors[i]);
    }

    printf("\n");

    return 0;
}