Автор | Сообщение |
|
Отправлено: 04.01.22 15:21. Заголовок: P-00 (25) (задача из примера, ошибка в алгоритме)
Здравствуйте! Суть задачи в том, чтобы найти на отрезке числа, которые получаются перемножением двух разных простых чисел (у числа должно быть 4 делителя). Муфаззалов Д.Ф. предлагает решение "без проверки на полный квадрат, так как если число является полным квадратом, то оно имеет нечетное количество делителей" - это все верно, но предложенный алгоритм даст ложные срабатывания, потому что цикл не доходит до корня из числа и счетчик это не учитывает. Сам алгоритм: #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; } } } Если его попробовать на числе 16, то получится закономерный итог "1 2 8 16". Если до корня из числа дойти, то число 16 не учтется, зато теперь число 25 проскочит "1 5 5 25". Так что в любом случае какая-то проверка на квадрат нужна. Проще всего сразу извлекать корень и если окажется, что рассматриваемое число это квадрат другого числа, то дальше не искать делители и переходить к следующему числу if (pow(int(sqrt(n)), 2) == n) continue; Алгоритм работает только потому, что попался удачный отрезок. Дальше в объяснении несколько вариаций этого алгоритма с такой же проблемой.
|
|
|
Ответов - 13
[только новые]
|
|
|
Отправлено: 06.01.22 12:48. Заголовок: Можете попробовать н..
Можете попробовать написать решето Эратосфена и циклом идти по простым числам, псевдокод: for i in range (0, n): for j in range (i+1, n): ... или делать проверку на простоту числа, но тогда i =2;i<sqrt(maxLength), j = i+1;j<sqrt(maxLength). Примерно так.
|
|
|
|
Отправлено: 06.01.22 13:58. Заголовок: zachto, как решить я..
zachto, как решить я знаю. Я пишу, что в материалах с объяснениями есть ошибка в алгоритме. Решение с решетом Эратосфена работает существенно дольше, даже если сгенерировать его до квадрата из правой границы. Перебирать его потом не нужно, быстрее с помощью решета искать количество простых делителей.
|
|
|
|
Отправлено: 06.01.22 14:24. Заголовок: Решето Эратосфена не..
Решето Эратосфена не нужно писать до квадрата правой границы.
|
|
|
|
Отправлено: 06.01.22 14:31. Заголовок: zachto, и докуда Вы ..
zachto, и докуда Вы предлагаете его генерировать? При переборе придется генерировать до правой границы, деленной пополам. При проверке на простоту, до корня из правой границы.
|
|
|
|
Отправлено: 06.01.22 14:41. Заголовок: Ты пишешь решето до ..
Ты пишешь решето до правой границы, пихаешь все найденные числа в вектор или список. Дальше перебираешь уникальные пары простых чисел.
|
|
|
|
Отправлено: 06.01.22 14:52. Заголовок: zachto, зачем правая..
zachto, зачем правая граница, если максимальное по величине простое число, которое теоретически возможно, умножается на 2? В худшем случае end = 2 * primeNumber - куда остальные-то генерировать? Вы границу видели правую? 194500, а можно сгенерировать до 97250 и ничего не потерять. У Вас все такие решения, как эти оба, о которых мы переписываемся?
|
|
|
|
Отправлено: 06.01.22 16:20. Заголовок: Справедливое замечан..
Справедливое замечание, однако ваше решение тоже можно ускорить. Например, простоту числа делать не за O(sqrt(n)), а за O(log(n)). Ваши решения все такие долгие?
|
|
|
|
Отправлено: 06.01.22 16:44. Заголовок: однако ваше решение ..
цитата: | однако ваше решение тоже можно ускорить |
| А где Вы мое решение увидели? Покажите, пожалуйста, тоже посмотреть на него хочу.
|
|
|
|
Отправлено: 06.01.22 17:51. Заголовок: И правда, раз вы ищи..
И правда, раз вы ищите ошибки в авторском решении, своего у вас нет. цитата: | Алгоритм работает только потому, что попался удачный отрезок |
| Опять удача, если меняете входные данные - задача становится другой. Вы хотите общее решение - пишите, присылайте на форум.
|
|
|
|
Отправлено: 06.01.22 18:14. Заголовок: Ага, так и запишем, ..
Ага, так и запишем, болтнули лишнего. цитата: | И правда, раз вы ищите ошибки в авторском решении, своего у вас нет. |
| А как одно из другого следует расскажите? Что у Вас с логикой? Теперь давайте еще немного о Вашей логике. Мы говорили о минимальной длине решета, а Вы начали подменять и пытаться говорить о скорости алгоритма на простоту числа. Проверить число по Ферма и я могу, но как это связано с определением минимальной длины решета? цитата: | Опять удача, если меняете входные данные - задача становится другой. |
| И снова проблема с логикой. Вы в алгоритме видите проверку на "удачность отрезка"? И я нет. Автору алгоритма просто повезло, потому что на глаз не определить, попадется ли на таком отрезке число из которого можно извлечь корень четвертой степени и получить простое число. цитата: | Вы хотите общее решение - пишите, присылайте на форум. |
| У Вас снова какие-то проблемы с сооброжалкой. Алгоритм и так является общим решением, а как его пофиксить я тоже указал. Полюбите общие решения и у Вас уменьшатся проблемы с логикой.
|
|
|
|
| Администратор
|
Сообщение: 3162
|
|
Отправлено: 08.01.22 12:50. Заголовок: beep пишет: Муфаззал..
beep пишет: цитата: | Муфаззалов Д.Ф. предлагает решение "без проверки на полный квадрат, так как если число является полным квадратом, то оно имеет нечетное количество делителей" - это все верно, но предложенный алгоритм даст ложные срабатывания, потому что цикл не доходит до корня из числа и счетчик это не учитывает. |
|
Спасибо, автор добавил в свои программы проверку на полный квадрат (см. файл ege25.doc).
|
|
|
|
|
Отправлено: 08.01.22 12:50. Заголовок: ДФ
Спасибо за обнаруженную ошибку. Исправленное решение выслано Константину Юрьевичу.
|
|
|
|
Отправлено: 11.01.22 12:52. Заголовок: Поляков, ДФ, вам спа..
Поляков, ДФ, вам спасибо за вашу работу и за такие возможности.
|
|
|
|