Невозможно вычислить простые множители с числом из 12 цифр в C

Question

Я пытаюсь узнать больше о C-коде, пытаясь сделать примеры на странице проекта Eular: http://projecteuler.net/problems В данный момент я пытаюсь вычислить наивысший простой множитель из числа 600851475143. Вот мойкод:

/* The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?*/
#include <stdio.h>

unsigned long long GetPrimeFactor(unsigned long long number)
{
    /* printf("The number you typed was %d\n", number);*/
    unsigned long long prime = 2;
    unsigned long long LargestPrime = 0;

    while (prime != 0)
    {
        if(number%prime == 0)
        {
            if(number == prime)
            {
                if(LargestPrime < prime)
                    LargestPrime = prime;

                printf("End of prime factors \nLargest Prime: %d\nEnding Number: %d\n", LargestPrime, number);
                break;
            }
            else if(LargestPrime < prime)
                LargestPrime = prime;

            //divide number by prime

            number = number/prime;
            printf("Prime: %d\n", prime);
        }

        else
        {
            //get new prime
            prime = nextPrimeNumber(prime);
        }
    }
}

unsigned long long nextPrimeNumber(unsigned long long input)
{
    unsigned long long nextPrimeNumber;

    while(input !=0)
    {
        if( input < 0)
        {
            printf("The number you have entered is negative\n");
        }
        else if (input > 0)
        {
            nextPrimeNumber = input + 1;

            if(nextPrimeNumber%2 == 0 && nextPrimeNumber != 2)
            {
                nextPrimeNumber += 1;
            }

            while(!isPrime(nextPrimeNumber))
            {
                nextPrimeNumber += 2;
            }

            return nextPrimeNumber;
        }
    }
}

int isPrime(int number)
{
    int i;
    int prime = 1; //true

    if(number == 2)
        prime = 0; //false

    if(number%2 == 0 || number <= 1)
        prime = 0;
    else
    {
        for(i=3; i<sqrt(number) && prime == 1; i+=2)
            if(number%i == 0)
                prime = 0;
    }

    return prime;
}

int main(void)
{
    unsigned long long number;

    printf("Enter a Number: \n");
    scanf("%d", &number);
    GetPrimeFactor(number);

    return 0;
}

Этот код работает для числа 13195, которое есть в примере, но плохо работает, когда я пробую большие числа, и я не уверен, что не так.

вывод с большим числом600851475143: простое число: 3 простое число: 29 простое число: 5 простое: 5108231 и т. Д. Это не может быть правильным, потому что число не может быть делится на 3 в любом случае.

Answer 1

Подпись ints до 2147483647, unsigned ints до 4294967295, вы можете использовать unsigned long long до 18446744073709551615, и если вам нужно что-то еще, используйте библиотеку произвольной точности / bignum, такую ​​как GnuMP (http://gmplib.org/)

Обновление отредактированного вопроса:

Спецификатор формата для scanf, который вы используете, даже не читает полностью unsigned long long, я где-то читал, что вы должны использовать %llu, однако на моем gcc это не работает, я должен использовать:

printf("Enter a Number: \n");
scanf("%I64d", &number);
printf("%I64d", number);  // <- make sure that this prints the number you 
                 // gave it before even calling GetPrimeFactor()

Answer 2

вы меняли scanf?

scanf("%L", &number)