потом я ввожу число за пределами int64

так я к тому что оценить человека можно потому какие он вопросы задает

и как реализует

и как учитывает новую информацию (уточнения)

и что иногда этими уточнениями можно не хило человеку переписывать

да банально даже сделает ли человек проверку на -25

если число введено отрицательное

если только очень далеко за пределами int64

вот из таких мелочей можно и узнать уровень человека

если только очень далеко за пределами int64

разложения большого числа даже в пределах int может на долго подвесить компьютер

не. на саомо деле есть признаки делимости

потому что там очень много операций деления и очень много поиска простых чисел

не. на саомо деле есть признаки делимости

ты сейчас сделаешь математическое открытие ?)))

на тему простых чисел

суть в том что этот алгоритм выглядит вот так

надо в начале в цикле перебрать все числа от 2 до n/2 и искать простые числа

потом зная простые числа надо пытаться разложить на множители подставляя разные комбинации

нахрена все то?

а почему бы по ходу дела не проверять

это к тому что собеседование и если человек не хочет писать код и ссылается на готовые штуки

то вот я привел пример задачи где готовой штуки нету

верней если даже они и есть всегда можно сделать чтобы они подвисли

ну.. другое дело она не практическая

и спросить человека а что это оно висит

и ему придется лесть во внутренности

так практическая задача по разработке портала займет около 8ч

твоего времени

а задачка вот с таким алгоритмом минут 15

чтобы понять уровень программиста

вот поэтому и берут простые задачи а не разработки крупных проектов которые практически более целесообразные

ну.. другое дело она не практическая

на базе таких простых чисел держиться алгоритм rsa который по умолчанию применяется в ssh

это к вопросу о практичесности

и применимости

до тех пор пока такая задача не решена алгоритм rsa надежен

ну смотри. задача сводится к поиску наименьшего делителя.. (для проверки)

так фишка в том что может быть число 29 например

29 = 5х5 + 2х2

потому 1. если число заканчивается на 0,2,4,6,8 то оно не простое и делится :) уже убрали половину операция

той половины что осталось хватит на долго

ты убрал не половину операций

а рассмотрел частный случай если число четное

если сумма чисел делиться на 3 - число делиться на 3

но если оно не четное то все операции остануться на месте

пример тебе 29

я знаю

потому что это задача с заебом

а рассмотрел частный случай если число четное

если число четное, нет смысла считать обе части - потому что набор делителей будет одинаков

и если человек юзает готовые решения

точно так же и если делится на 3

вот на этой задаче он прикурит

тогда считать в 3 раза меньше :))

ну и т.д

если число четное, нет смысла считать обе части - потому что набор делителей будет одинаков

суть в том что ты потом задачу сводишь к разложению на простые числа

потому что есть теорема что любое не простое число может быть разложенно на простые множители

ну да

и ты потом человека подводишь к этому

и требуешь разложения на простые множители

и вот твой вариант с четностью идет в помойку

как и сумма чисел числа если делиться на 3

я говорю что эта задача с подвохом)

и исходя из уровня знаний человека

ну если не срабатываю признаки делимости на 2, 3, 5, то скорее всего число простое :))

но опять же не всегда)

https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%BE_%D0%9C%D0%B5%D1%80%D1%81%D0%B5%D0%BD%D0%BD%D0%B0#%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE_%D0%9C%D0%B5%D1%80%D1%81%D0%B5%D0%BD%D0%BD%D0%B0

ну если не срабатываю признаки делимости на 2, 3, 5, то скорее всего число простое :))

121 например

не простое и не делиться на те числа что ты написал

Свойство числа быть простым называется простотой. Простой, но медленный метод проверки простоты заданного числа n известен как перебор делителей. Он состоит из проверки того, является ли {\displaystyle n} n кратным целому числу от {\displaystyle 2} 2 до {\displaystyle {\sqrt {n}}} {\sqrt {n}}

это если в лоб

а вот это юзают обычно https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D1%81%D1%82_%D0%90%D0%B3%D1%80%D0%B0%D0%B2%D0%B0%D0%BB%D0%B0_%E2%80%94_%D0%9A%D0%B0%D1%8F%D0%BB%D0%B0_%E2%80%94_%D0%A1%D0%B0%D0%BA%D1%81%D0%B5%D0%BD%D1%8B

существуют точные и вероятностные алгоритмы

и суть в том что на собеседование если человек что то подобное сразу говорит

это значит что у него скорей всего хороший математический бэкграунд

ну просто ты сказал чтто сложность вычисления n/2

не говорил я такова)))

я с этим не согласился

надо в начале в цикле перебрать все числа от 2 до n/2 и искать простые числа

вот тут говорил

так этот n/2 это только первый шаг по поиску простых чисел

а я говорю что нифига не так :)

потом надо еще переборы делать для каждого простого числа

потом когда ты узнал простые числа надо проверить входное число что не простое