целочисленная константа слишком велика для длинного типа при поиске наибольшего простого множителя

Я работаю над решением проекта Эйлера 3:

Description: The prime factors of 13195 are 5, 7, 13 and 29.
             What is the largest prime factor of the number 600851475143 ?

Это мой код для генерации ответа. Однако мне нужен целочисленный тип для хранения 600851475143. Когда я компилирую это в GCC на Mac, я получаю:

integer constant is too large for ‘long’ type".

Я ожидаю, что long long может легко удержать это число. Я также пытался сделать его неподписанным. Почему мой код не содержит это небольшое число и что я могу сделать, чтобы заставить его работать?

#include <iostream>
#include <vector>

using namespace std;

static bool IsPrimeFactor(int numToTest,int testNum,vector<int> factors)
{
    if(numToTest%testNum==0) // is it a factor?
    {
        // see if it is a prime factor
        for(unsigned int i=0; i < factors.size(); i++)
        {
            if(testNum%factors[i]==0)  // see if this factor
            {                          //is divisble by one we have already

                return false;
            }
        }

        return true;
    }
    return false;
}

int main() {
    unsigned long long numToTest=600851475143;
    unsigned int testNum=2;  // 0 and 1 are assumed
    vector<int> factors;   

    while(testNum<numToTest)   // don't go higher than the max num
    {
        if(IsPrimeFactor(numToTest,testNum,factors)) // is it a factor?
        {
            factors.push_back(testNum); // got through prime factors 
        }                                   // and none divided it

        testNum++;
    }

    for(unsigned int i=0; i < factors.size(); i++)
    {
        cout << "factor " <<factors[i] << endl;
    }

    cout<<"Highest factor: " << factors[factors.size()-1]<<endl;

    return 0;
}

c++ prime-factoring
person Maestro1024    schedule 25.01.2011    source источник
comment
У вас есть серьезные концептуальные проблемы в вашем коде - я не хочу портить вам удовольствие от работы с проектом Эйлера, но вы можете немного прочитать о том, как сделать простую факторизацию;)   -  person etarion    schedule 25.01.2011

Ответы (2)


arrow_upward
6
arrow_downward

Проверьте этот вопрос. Вы должны указать свой литерал следующим образом:

600851475143LL
person Björn Pollex    schedule 25.01.2011
comment
Начиная с C++11, десятичная целочисленная константа без суффикса имеет тип int, long int или long long int, в зависимости от ее типа. В C++03 это было int или long int -- потому что типа long long int еще не существовало. Соответствующий компилятор, поддерживающий long long int, должен принимать такой литерал без суффикса, но более старый компилятор, поддерживающий long long int в качестве расширения, может не принимать. Вызов компилятора с помощью -std=c++11 или его эквивалента (если ваш компилятор его поддерживает) должен работать. С другой стороны, добавление суффикса LL безвредно и, возможно, понятнее. - person Keith Thompson; 22.01.2015

arrow_upward
1
arrow_downward

Как сказал @Space_C0wb0y, вам нужно указать суффикс для литерала.

Кроме того, у вас возникнут проблемы с вашей функцией IsPrimeFactor — параметры представляют собой целые числа, но, как вы уже обнаружили, целое или даже длинное число недостаточно велико для хранения числа, которое вы будете передавать повторно. ..

person Jon    schedule 25.01.2011
comment
Спасибо. Я знаю, что эта функция потребует некоторого рефакторинга. - person Maestro1024; 25.01.2011