CODEWITHSUNDEEP
cmathbigintegerinteger-division
silentcontributor
silentcontributor

Reputation: 85

How to divide stupidly big numbers in C

Am learning C and thought that Project Euler problems would be a fun and interesting way to learn (and would kill 2 birds with 1 stone because it would keep me thinking about maths as well) but I've hit a snag.

I have (what I think is) a good (if simple) algorithm for finding the largest prime factor of a number. It works (as far as I have tested it), but the PE question uses 600851475143 as it's final question. I have tried to use doubles and such, but I can never seem to find both a modulo and a division operator. Any help would be greatly appreciated.

Code attached is before I started to make it work with doubles (or any other type):

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

void main() {
    int target, divisor, answer;
    target = 375;
    divisor = 2;
    answer = -1;

    answer = factorise (target,divisor);

    printf("Answer to Euler Problem 3: %i\n", answer);
}

int factorise(number, divisor) {
    int div;
    while (divisor < number) {
        div = divide(number,divisor);
        if (div) {number = div;}
        else {divisor++;}
    }
    return divisor;
}

int divide(a,b) {
    if (a%b) {return 0;}
    else {return a/b;}
}

Upvotes: 2

Views: 2942

Answers (3)

pmg
pmg

Reputation: 108978

The C Standard specifies the lower limit for integral types:

char: 127 (2^7 - 1)
short: 32767 (2^15 - 1)
int: 32767 (2^15 - 1)
long: 2147483647 (2^31 - 1)
long long (C99): 9223372036854775807 (2^63 - 1)

If Project Euler uses a C99 compiler you're guaranteed with long long.

Also, these are minimum values. I think Project Euler's longs are 64 bits, so long should also work for C89.

Upvotes: 2

robert
robert

Reputation: 34398

Have you tried long or long long? Depending on your compiler, those might work. But you'll eventually need a bigint library for other PE problems. There are some on the internet, but since you're doing this to learn I'd suggest writing your own.

Upvotes: 4

Kos
Kos

Reputation: 72241

The biggest integral type in C99 is long long, you can try this one.

You cannot make precise integral calculations with double as it's imprecise with big numbers.

Upvotes: 1

Related Questions