Ошибка при решении Project Euler сумма № 3 в C ++

Question

Это мой код:

#include <iostream>

using namespace std;

int main()
{
    long int x = 1;
    long int res;

    while (x<600851475143)
    {
        x++;
        if(600851475143%x==0)
        {
            res=x;
            cout<<x<<"\n";
        }
    }
}

Я не знаю, что с ним не так, но он дает мне такой вывод:

839
1471
6857
59569
104441
486847
1234169
5753023
10086647
87625999
408464633
716151937
-716151937
-408464633
-87625999
-10086647
-5753023
-1234169
-486847
-104441
-59569
-6857
-1471
-839
-71
-1
Floating point exception

Process returned 136 (0x88)  execution time : 156.566 s
Press ENTER to continue.

и когда я заменяю 600851475143 на 13195 [что было в примере] ... он работает нормально ... и дает мне такой вывод:

5
11
55
11149

Process returned 0 (0x0) execution time : 0.005 s
Press ENTER to continue.

Я не знаю, что я делаю неправильно ... :/ Возможно, моя предыдущая программа не работала должным образом ... Сначала я попробовал ее с int, а затем изменил на long int ... Без разницы ...

Answer 1

Когда ваше положительное число внезапно становится отрицательным после ++, это верный признак целочисленного переполнения . Вам нужно выбрать тип данных, который может содержать большие целые числа, например, long long.

Кстати, ваш алгоритм не ищет наибольшего простого фактора, как требуется в задаче. Он ищет самый большой фактор, который не обязательно является основным.

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

Answer 2

Отрицательные значения из-за переполнения. Начните с использования целых чисел без знака вместо целых чисел со знаком. Кроме того, в 32-разрядных компьютерах типы long int и int имеют 32-разрядную версию.

unsigned long long int x = 1;
unsigned long long int res;

Кроме того, вы могли бы подчеркнуть тот факт, что эти константы без знака

while (x<600851475143U)
    {
        x++;
        if(600851475143U%x==0)
        {
            res=x;
            cout<<x<<"\n";
        }
    }

Answer 3

Код ниже покажет все основные факторы числа, введенного пользователем. Но 600851475143 - слишком большое число, чтобы найти его основные факторы.Измените эту программу, чтобы увидеть основные факторы 600851475143, а также измените ее, чтобы выяснить, какой из них является основным.Я выучил c ++ только два месяца, поэтому могу помочь вам только в этом. Все лучшее.

            #include<iostream.h>
            #include<conio.h>
            class primefactor
                 {
                    unsigned long int a;
                  public:
                            void factor();

                  };
           void primefactor::factor() 
                 {
                     cout<<"Enter any number to see its prime factors";
                     cin>>a;
                     int count=0;
                     int count1=0;
                     for(unsigned long int loop1=a;loop1>=1;loop1--)
                         {
                            if(a%loop1==0)
                              {
                                 for(unsigned long int loop=loop1;loop>=1;loop--)
                                       {
                                         if(loop1%loop==0)
                                              {
                                                  count++;
                                               }
                                         }
                             if(count==2)
                                {
                                    count1++;
                                    cout<<loop1<<"\t";
                                 } 
                          }
                     count=0;
                    }
                       cout<<"\n"<<"There are"<<count1<<"\t"<<"prime factors";
                 }

           void main()
                 {
                    primefactor k;
                       clrscr();
                    k.factor();
                       getch();
                  }

Answer 4

попробуйте использовать unsigned long long, в нем должно быть не менее 18,446,744,073,709,551,615 (это число я даже не могу представить).

Answer 5

Ваши типы переменных не могут содержать 12-значные числа. Типичный unsigned long int может хранить от 0 до 4 294 967 295, для подписанных - от 2 147 483 648 до 2 147 483 647.