Где ошибка в решении?

Question

[til_down]

Условие: "Простые делители числа 13195 - это 5, 7, 13 и 29.
Каков самый большой делитель числа 600851475143, являющийся простым числом?"
Вот код:

#include <iostream>
using namespace std;

long long number = 600851475143;
int del = 0;

int main(int argc, char const *argv[])
{
	for (int i = 2; i < number; i++)
	{
		if (number % i == 0)
		{
			for (int j = 2; j < i; j++)
			{
				if (i % j == 0)	
					break;
				else
					del = i;	
			}	
		}
	}	
	cout << del << endl;
	return 0;
}

Answer 1

[Wataru]

У вас number в int не помещается. А вы цикл гоните от 2 до number. У вас условие i < number в цикле будет всегда выполнятся - потому что ну не может int i быть больше number.

edit: И вообще логика проверки на простоту у вас сломана. del = i выполнится для любого j, такого что i на него не делится. Т.е. если i=6, то при j=5 вы dеl перезапишите. Вам надо в цикле устанавливать bool flag. И, после цикла на него смотреть.

Comments

[galaxy]

тут бы еще условие поменять на i*i <= number (и заодно j*j <= i), а то результата можно и не дождаться

[Wataru]

galaxy, Я бы вообще по-другому делал. Я бы сразу сокращал number на i, пока делится. Это самое i в таком подходе всегда будет простым. Даже внутреннего цикла не надо.

[til_down]

Wataru,

И вообще логика проверки на простоту у вас сломана. del = i выполнится для любого j, такого что i на него не делится.

. Спасибо за замечание. Исправил, проверил на числах поменьше. Работает, вроде, правильно. Но основная проблема сохранилась. Все еще ничего не выводит. Быть может с++ не может справиться с такими огромными значениями? И надо подойти к решению, используя алгоритмы для работы с большими числами?
Обновленный код:

#include <iostream>
using namespace std;

long long number = 600851475143; long long del = 0;
bool flag = true;

int main(int argc, char const *argv[])
{
	for (long long i = 2; i < number; i++)
	{
		flag = true;
		if (number % i == 0)
		{
			for (long long j = 2; j < i; j++)
			{
				if (i % j == 0)
				{
					flag = false;
					break;
				}	
			}
			if (flag)
				del = i;	
		}	
	}
	cout << del << endl;	
	return 0;
}

[Wataru]

til_down, Конечно, оно не справляется. Один только цикл до 600851475143 будет выполнятся минут 10. А там внутри ведь еще и цикл для проверки. Я думаю, ваше решение будет пару часов работать.

Однако, если вы будете сокращать number на i (number /= i;), пока оно делится (может, придется кучу раз сокращать), то не надо внутреннего цикла - i всегда будет простым.

Вторая оптимизация - можно остановиться, когда i*i > number. Тогда оставшееся number, если оно больше 1, будет каким-то простым числом.

Это все работает, потому что мы поддерживаем инвариант - number не делится ни на одно число, меньшее i (кроме 1, конечно). Поэтому надо циклом while сокращать i пока можно. Поэтому, если number делится на i, то i - простое. Ведь иначе был бы меньший i делитель number. Поэтому при i*i>number, number - простое, ведь иначе у него был бы какой-то делитель, меньший i.

Это решение будет работать сильно быстрее.

[til_down]

Wataru, большое спасибо! Решил использовать второй метод. Ответ вывел правильно.
Я решил разобраться, почему данный способ работает, но не смог понять. Потому как, работает он не для всех чисел. К примеру, если в качестве вводимого числа использовать 246 - программа выводит 3, хотя должна вывести 41.Можете объяснить почему?

И ещё, если есть возможность, можете написать(в виде кода) ваш способ решения -

Однако, если вы будете сокращать number на i (number /= i;), пока оно делится (может, придется кучу раз сокращать), то не надо внутреннего цикла - i всегда будет простым.

И объяснить как он работает?

Заранее спасибо, вы мне очень помогли)

[Wataru]

til_down,

Вот этот код выведет все простые делители числа.

long long i = 2;
while (i*i <= number) {
  if (number % i == 0) {
    while (number % i == 0) number /= i;
    cout << i;
  }
  ++i;
}
if (number > 1) cout << number;

Идея в сокращении младшего простого делителя целиком. Этот код работает, потому что поддерживается инвариант, что number не делится ни на одно число, меньшее i. Поэтому, когда оно делится на i, то i простое.

По идее можно было бы гнать цикл пока i <= number, но можно делать i*i
Не совсем понял, какой метод вы в итоге используете, но возможно проблема с последним простым делителем. Может так получиться, что после какого-то сокращение number останется простым числом, меньшим i*i. Поэтому после цикла надо проверить, вдруг number не 1.

[til_down]

Wataru, спасибо, понял)

Не совсем понял, какой метод вы в итоге используете

Я решил сделать следующим образом:

for (long long i = 2; i * i < number; i++)
	{
		flag = true;
		if (number % i == 0)
		{
			for (long long j = 2; j * j < i; j++)

Меня смущает, то что, этот подход работает не со всеми числами. Для 600851475143 выводит правильно. А для 246, результат 3, хотя должен быть 41

[Wataru]

til_down, Тут та же проблема. i перебирает только делители до корня. Если есть делитель больше sqrt(number), как 41 > sqrt(246), то вы его никогда не рассмотрите.

Решение тут - это рассматривать не только i, но и number / i в качестве делителя. Тогда вам надо внутри сделать 2 цикла по j для проверки i и number/i.

[til_down]

Wataru, огромное вам спасибо за ответы и ваше терпение! Вы мне очень помогли!