Одинадцята лекція третього сезону відбудеться 1 грудня о 18 годині у конференц-залі на третьому поверсі.
Лекція містить матеріал підвищеної складності.
Лекцію веде Shef.
Тема: Ефективні алгоритми факторизації чисел.
На порядку денному:
- Тести на простоту.
- І знову решето Ератосфена.
- Алгоритми факторизації.
Перелік задач, рекомендованих до розв’язання згідно теми лекції:
acm.lviv.ua 1274 – Цукерки:
(http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1274)
UVA 10858 – Unique Factorization
(http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1799)
UVA 10392 – Factoring Large Numbers
(http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1333)
TJU 3766 – Monday-Saturday Prime Factors
(http://acm.tju.edu.cn/acm/showp3766.html)
Перелік джерел, рекомендованих до ознайомлення:
Лінійний алгоритм побудови решета Ератосфена
(http://www.cs.utexas.edu/users/misra/scannedPdf.dir/linearSieve.pdf)
Алгоритм факторизації Шермана Лемана
(http://www.ams.org/journals/mcom/1974-28-126/S0025-5718-1974-0340163-2/S0025-5718-1974-0340163-2.pdf)
Лінки на UVA здається не працюють.
У мене вони чудово працюють. Можливо ще хтось пробував?
Та, там все ок, просто Хром чомусь каже, що забагато перереадресацій. Firefox нормально відкрив.
Здав *TJU 3766 – Monday-Saturday Prime Factor*, але там така штука – там multiple tests, і в мене , якщо пробувати всі 300000 можливих значення, прога працює десь близько 8 секунд. В тестах менше тестів, і в мене AC, але чи можна то якось оптимізувати?