Отправлено: 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;

Алгоритм работает только потому, что попался удачный отрезок. Дальше в объяснении несколько вариаций этого алгоритма с такой же проблемой.

 Отправлено: 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. Заголовок: Ага, так и запишем, ..

Ага, так и запишем, болтнули лишнего.

цитата:

И правда, раз вы ищите ошибки в авторском решении, своего у вас нет.

А как одно из другого следует расскажите? Что у Вас с логикой?

Теперь давайте еще немного о Вашей логике. Мы говорили о минимальной длине решета, а Вы начали подменять и пытаться говорить о скорости алгоритма на простоту числа. Проверить число по Ферма и я могу, но как это связано с определением минимальной длины решета?

цитата:

Опять удача, если меняете входные данные - задача становится другой.

И снова проблема с логикой. Вы в алгоритме видите проверку на "удачность отрезка"? И я нет. Автору алгоритма просто повезло, потому что на глаз не определить, попадется ли на таком отрезке число из которого можно извлечь корень четвертой степени и получить простое число.

цитата:

Вы хотите общее решение - пишите, присылайте на форум.

У Вас снова какие-то проблемы с сооброжалкой. Алгоритм и так является общим решением, а как его пофиксить я тоже указал. Полюбите общие решения и у Вас уменьшатся проблемы с логикой.

 Отправлено: 08.01.22 12:50. Заголовок: beep пишет: Муфаззал..

beep пишет:

цитата:

Муфаззалов Д.Ф. предлагает решение "без проверки на полный квадрат, так как если число является полным квадратом, то оно имеет нечетное количество делителей" - это все верно, но предложенный алгоритм даст ложные срабатывания, потому что цикл не доходит до корня из числа и счетчик это не учитывает.

Спасибо, автор добавил в свои программы проверку на полный квадрат (см. файл ege25.doc).

 Отправлено: 08.01.22 12:50. Заголовок: ДФ

Спасибо за обнаруженную ошибку. Исправленное решение выслано Константину Юрьевичу.

 Отправлено: 11.01.22 12:52. Заголовок: Поляков, ДФ, вам спа..

Поляков, ДФ, вам спасибо за вашу работу и за такие возможности.