Как разделить тупо большие числа в C - PullRequest
Новая
       47

Как разделить тупо большие числа в C

2 голосов
/ 13 декабря 2010

Я изучаю C и думаю, что Project Euler проблемы будут забавным и интересным способом изучения (и они убьют 2 зайцев одним выстрелом, потому что это также заставит меня думать о математике), но я 'Мы натолкнулись на загадку.

У меня есть (как мне кажется) хороший (хотя и простой) алгоритм для нахождения наибольшего простого множителя числа.Это работает (насколько я это проверял), но вопрос PE использует 600851475143 в качестве последнего вопроса.Я пытался использовать удваивания и тому подобное, но я никогда не смогу найти ни по модулю, ни по оператору деления.Любая помощь будет принята с благодарностью.

Код прилагается до того, как я начал работать с двойными (или любыми другими) типами: 

#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;}
}

Ответы [ 3 ]

4 голосов
/ 13 декабря 2010

Вы пробовали long или long long?В зависимости от вашего компилятора, они могут работать.Но в конечном итоге вам понадобится библиотека bigint для других задач PE.В Интернете есть некоторые, но, поскольку вы делаете это, чтобы узнать, я бы предложил написать свой собственный.

2 голосов
/ 13 декабря 2010

Стандарт C определяет нижний предел для целочисленных типов: 

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)

Если Project Euler использует C99 компилятор, вы гарантированно используете long long.

Также минимальные значения.Я думаю, что Project Euler long является 64-битным, поэтому long также должен работать для C89.

1 голос
/ 13 декабря 2010

Самый большой целочисленный тип в C99 - long long, вы можете попробовать этот.

Вы не можете делать точные интегральные вычисления с double, поскольку он неточен с большими числами.

...