@o_ouch

Как решить задачу на поиск простых множителей?

Необходимо решить данную задачу:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?


Написал след. код:
#include <iostream>
 
int main()
{
    std::cout << "Hello World!\n";
    unsigned long long C = 600851475143;
    unsigned long long temp= 1;
    unsigned long long temp2 = 0;
    while  (C > 1)
    {
        temp = C;
        C--;
      
        if (C % temp == 0) {
            if ((temp % 2 != 0) && (temp % 3 !=0)) {
                if (temp2 < temp) { temp2 = temp; }
            }
        }
    }
    std :: cout << temp2;
}


Но программа компилится и выдает только строку хелоу ворлд.
В каком месте искать ошибку?
  • Вопрос задан
  • 68 просмотров
Пригласить эксперта
Ответы на вопрос 1
@romancelover
программист C++ под Linux
Программа пытается проверять на делимость все числа от 600851475143 подряд, и на этом зависает (слишком много проверок нужно выполнить). Переменная С уменьшается только вычитанием единицы.
И считает она не то, что нужно.
Я поправил так (самый простой код, можно ещё оптимизировать, например, проверять числа до корня квадратного из делимого, а не до делимого). Но для новичка сойдёт.
#include <iostream>
int main()
{
    std::cout << "Hello World!\n";
    unsigned long long C = 600851475143;
    unsigned long long temp=3;
    if((C % 2) == 0)
    {
        C = C / 2;
        std::cout << 2 << std::endl;
    }
    while  (C > 1)
    {
        if (C % temp == 0) {
            C = C / temp;
            std::cout << temp << std::endl;
        }
        temp=temp+2;
    }
}

Вывод:
Hello World!
71
839
1471
6857
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы