2

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;}
}
Zero Piraeus
  • 56,143
  • 27
  • 150
  • 160
silentcontributor
  • 85
  • 1
  • 7

3 Answers3

4

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.

robert
  • 33,242
  • 8
  • 53
  • 74
  • I'm pretty sure my compiler is won't do anything useful with long or long long, so it seems that I'll be making my own bigint library! Thanks. – silentcontributor Dec 13 '10 at 14:40
  • 1
    "but since you're doing this to learn I'd suggest writing your own" ???? Writing correct mathematical libraries of any kind can be fiendishly difficult. If doing to learn, that's one thing, but if doing to use regularly, I would always prefer a reputable library built by someone who knows how to do it correctly. (And this is coming from someone who has written plenty of math library functions in his time) – Jason S Dec 13 '10 at 14:58
  • @Jason S The original question is for Project Euler, not for production code. – robert Dec 13 '10 at 15:23
  • A good/bad foundation has the same effect on a project, whether it's a hobby or a production effort. To continue the metaphor, if I had cement of questionable quality, I would not want to use it either for a backyard shed or for a large apartment building. If I wanted to learn about making my own cement, I'd make that its own test project; I wouldn't use it for the backyard shed. – Jason S Dec 13 '10 at 15:26
2

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.

pmg
  • 106,608
  • 13
  • 126
  • 198
1

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.

Kos
  • 70,399
  • 25
  • 169
  • 233