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

Question

[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;
}

Но программа компилится и выдает только строку хелоу ворлд.
В каком месте искать ошибку?

Comments

[xorknown]

Напишите сначала алгоритм обычным языком. У вас большие проблемы с ним. Зачем вы начинаете проверять числа начиная с C - 1. Какой ближайший делитель для этого числа? Я думаю C / 2. Как вы определяете простое число, уверены что верно?

[o_ouch]

xorknown, понял, спасибо
пересмотрю свой вопрос и построю для начала алгоритм решения ..

[xorknown]

o_ouch, Но если по вопросу, то вроде он у вас работает, хоть и неправильно, просто работает очень долго и поэтому не выводит строку.

[Сергей Соколов]

Может, поможет: https://www.geeksforgeeks.org/print-all-prime-numb...

[Сергей Соколов]

Ну и освежите математику, свойства простых чисел.
Делители исходного будут не больше, чем его половина. Можно начинать идти вниз, начиная от половины и искать делители. Очередной проверять, простое ли число. Как только простое – вот оно, наибольшее.

Answer 1

[Николай]

Программа пытается проверять на делимость все числа от 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

Comments

[Николай]

если нужно вывести последнее число, с проверкой до корня:
#include
#include
int main()
{
std::cout << "Hello World!\n";
unsigned long long C = 600851475143;
unsigned long long temp=3;
unsigned long long maxopt;
if((C % 2) == 0)
{
C = C / 2;
}
maxopt=sqrt(C)+1;
do
{
if (C % temp == 0) {
C = C / temp;
maxopt=sqrt(C)+1;
}
temp=temp+2;
}
while(temp<=maxopt);
std::cout << C << std::endl;
}
вывод:
Hello World!
6857