Форум » Обработка целых чисел » P-00 (25) (задача из примера, ошибка в алгоритме) » Ответить
P-00 (25) (задача из примера, ошибка в алгоритме)
beep: Здравствуйте! Суть задачи в том, чтобы найти на отрезке числа, которые получаются перемножением двух разных простых чисел (у числа должно быть 4 делителя). Муфаззалов Д.Ф. предлагает решение "без проверки на полный квадрат, так как если число является полным квадратом, то оно имеет нечетное количество делителей" - это все верно, но предложенный алгоритм даст ложные срабатывания, потому что цикл не доходит до корня из числа и счетчик это не учитывает. Сам алгоритм: [pre2]#include <iostream> int main() { const int divCount =4; int divs[divCount],i,d; for( int n = 194455; n <= 194500; n++ ) { int count = 0; for( d = 1; d*d < n; d++ ) if( n % d == 0 ) { divs[count/2] = d; divs[divCount-count/2-1]=n/d; count+=2; if( count > divCount ) break; } if (count == divCount) { for( i = 0; i < divCount; i++ ) std::cout << divs[ i] << ' '; std::cout << std::endl; } } } [/pre2] Если его попробовать на числе 16, то получится закономерный итог "1 2 8 16". Если до корня из числа дойти, то число 16 не учтется, зато теперь число 25 проскочит "1 5 5 25". Так что в любом случае какая-то проверка на квадрат нужна. Проще всего сразу извлекать корень и если окажется, что рассматриваемое число это квадрат другого числа, то дальше не искать делители и переходить к следующему числу [pre2]if (pow(int(sqrt(n)), 2) == n) continue;[/pre2] Алгоритм работает только потому, что попался удачный отрезок. Дальше в объяснении несколько вариаций этого алгоритма с такой же проблемой.
Ответов - 13
zachto: Можете попробовать написать решето Эратосфена и циклом идти по простым числам, псевдокод: [pre2]for i in range (0, n): for j in range (i+1, n): ...[/pre2] или делать проверку на простоту числа, но тогда i =2;i<sqrt(maxLength), j = i+1;j<sqrt(maxLength). Примерно так.
beep: zachto, как решить я знаю. Я пишу, что в материалах с объяснениями есть ошибка в алгоритме. Решение с решетом Эратосфена работает существенно дольше, даже если сгенерировать его до квадрата из правой границы. Перебирать его потом не нужно, быстрее с помощью решета искать количество простых делителей.
zachto: Решето Эратосфена не нужно писать до квадрата правой границы.
beep: zachto, и докуда Вы предлагаете его генерировать? При переборе придется генерировать до правой границы, деленной пополам. При проверке на простоту, до корня из правой границы.
zachto: Ты пишешь решето до правой границы, пихаешь все найденные числа в вектор или список. Дальше перебираешь уникальные пары простых чисел.
beep: zachto, зачем правая граница, если максимальное по величине простое число, которое теоретически возможно, умножается на 2? В худшем случае end = 2 * primeNumber - куда остальные-то генерировать? Вы границу видели правую? 194500, а можно сгенерировать до 97250 и ничего не потерять. У Вас все такие решения, как эти оба, о которых мы переписываемся?
zachto: Справедливое замечание, однако ваше решение тоже можно ускорить. Например, простоту числа делать не за O(sqrt(n)), а за O(log(n)). Ваши решения все такие долгие?
beep: однако ваше решение тоже можно ускорить А где Вы мое решение увидели? Покажите, пожалуйста, тоже посмотреть на него хочу.
zachto: И правда, раз вы ищите ошибки в авторском решении, своего у вас нет. Алгоритм работает только потому, что попался удачный отрезок Опять удача, если меняете входные данные - задача становится другой. Вы хотите общее решение - пишите, присылайте на форум.
beep: Ага, так и запишем, болтнули лишнего. И правда, раз вы ищите ошибки в авторском решении, своего у вас нет. А как одно из другого следует расскажите? Что у Вас с логикой? Теперь давайте еще немного о Вашей логике. Мы говорили о минимальной длине решета, а Вы начали подменять и пытаться говорить о скорости алгоритма на простоту числа. Проверить число по Ферма и я могу, но как это связано с определением минимальной длины решета? Опять удача, если меняете входные данные - задача становится другой. И снова проблема с логикой. Вы в алгоритме видите проверку на "удачность отрезка"? И я нет. Автору алгоритма просто повезло, потому что на глаз не определить, попадется ли на таком отрезке число из которого можно извлечь корень четвертой степени и получить простое число. Вы хотите общее решение - пишите, присылайте на форум. У Вас снова какие-то проблемы с сооброжалкой. Алгоритм и так является общим решением, а как его пофиксить я тоже указал. Полюбите общие решения и у Вас уменьшатся проблемы с логикой.
Поляков: beep пишет: Муфаззалов Д.Ф. предлагает решение "без проверки на полный квадрат, так как если число является полным квадратом, то оно имеет нечетное количество делителей" - это все верно, но предложенный алгоритм даст ложные срабатывания, потому что цикл не доходит до корня из числа и счетчик это не учитывает. Спасибо, автор добавил в свои программы проверку на полный квадрат (см. файл ege25.doc).
ДФ: Спасибо за обнаруженную ошибку. Исправленное решение выслано Константину Юрьевичу.
beep: Поляков, ДФ, вам спасибо за вашу работу и за такие возможности.
полная версия страницы