Новый ответ под тем же номером? С++

Итак, у меня есть эта программа:

#include <iostream>

using namespace std;


bool prime(int input)
{
//    cout << "pinput: " << input << endl;
    int i = ((input/2) + 1);
  //      cout << "pi: " << i << endl;
    int c;
    for (i>0; i--;){
        //cout << "pi: " << i << endl;
        if (input == 3 || input == 2){
         //   cout << "true" << endl;
            return true;
        }
        if (input == 1){
       //     cout << "pi = 1" << endl;
            return false;
        }
    c= input%i;
    if (c==0 || i == 1 ){
     //   cout << "false" << endl;
        return false;
    }
    else if (c!=0 && i<4){
   //     cout << "true" << endl;
        return true;
    }
    }
return 0;
}

int factor(int input){
//    cout << "finput: " << input << endl;
   int i = (input/2) + 1;
    int c;
    int e;
    bool d = false;
    for (i>0; i--;){
  // cout << "fi: " << i << endl;
        c = input%i;
        if (c==0){
        d = prime(i);
        if (d==true){
    //    cout << "found" << endl;
        return i;}
        }
        if (i==1){
  //          cout << "fi = 1";
            return 0;
        }
//cout << "not prime" << endl;
        }
    return 0;
}

int main(){
    int woot;
    cout << "Please insert quater: " <<endl;
    cin >> woot;
    int answer;
    answer = factor(woot);
    if (answer == 0)
    cout << "no prime factors" << endl;
    else
    cout << "answer is: " <<answer << endl;

return 0;
}

Кажется, это работает, пока я не введу действительно большое число, например, число 600851475143, и в этом случае я всегда получаю разные ответы, когда запускаю это число, теперь я почти уверен, что оно просто превышает размер его типа переменной. Теперь я искал и не могу найти правильный тип переменной для такого большого числа, я int и long, кажется, для чисел, которые предназначены для чисел до 4294967295, если без знака, однако это всего 10 цифр, у меня 12 , Какой тип переменной я должен использовать? Или это даже решит проблему? Программа состоит в том, чтобы найти наибольший простой делитель числа (задача Эйлера 3). Любые советы, ссылки или советы будут оценены. И, конечно же, ответ очень ценится! :D