Прогресс в вычислениях простых чисел

[Linkey]

Возник вопрос, насколько продвинулась современная математика в вычислении простых чисел. Говоря более конкретно, какие вычислительные ресурсы необходимы для определения, является ли заданное число простым (сколько машинного времени и памяти)? Чему эти затраты пропорциональны – самому число, или его логарифму и т.д.?
Здесь надо рассмотреть три варианта:
1) Задано произвольное число $N$, например гугол плюс $1259$. Нужно определить, является ли оно простым.
2) Нужно эти вычисления провести для всех чисел от $1$ до $N$, результаты можно заносить в память.

Самый очевидный способ определить, является ли число $N$ простым – перебрать все множители от $1$ до $N/2$ и посчитать, можно ли их умножением на другое число получить $N$. Т.е. количество времени пропорционально $N^2$, для обоих вариантов (два вложенных цикла).

[kp9r4d]

Раз уж вы этим заинтересовались, то подумайте вот о чём:
1) Проверку "можно ли их умножением на другое число получить $N$" можно сделать за константу, подумайте как.
2) Перебирать можно не до $N/2$, а до числа куда более меньшего (при большом $N$). До какого?
Эти вопросы несложные и вполне вам под силу, подумайте.

[Linkey]

kp9r4d в сообщении #887322 писал(а):

) Проверку "можно ли их умножением на другое число получить $N$" можно сделать за константу, подумайте как.

Не понял, что значит “сделать за константу”?

kp9r4d в сообщении #887322 писал(а):

2) Перебирать можно не до $N/2$, а до числа куда более меньшего (при большом $N$). До какого?

Сразу ясно, что если $N$ записано в десятичной форме, то можно не проверять делимость на $2$ и $5$, но это мелочь, как я понимаю для остальных делителей этот метод ничего не даёт.
Я сразу подумал, что можно считать делители до $\sqrt{N}$ (вот она, интуиция!). Если мы перебрали все делители до $\sqrt{N}$, дальше можно не считать. Но во втором цикле приходится перебирать до N/n. Т.е. когда в первом цикле мы взяли первый делитель $3$, надо во втором перебрать все числа до $N/3$, когда взяли $5$ – все числа до $N/5$ и т.д., и когда взяли $\sqrt{N}$ – все числа до $\sqrt{N}$. Наверно в среднем получаются затраты времени $\sqrt{N}$.
Тут можно придумать ещё много хитростей, но эта задача скорее алгоритмическая, а не математическая. Например, можно составить список простых чисел и перебирать только их (если $N$ не делится на $3$, ясно что оно не будет делиться и на $6$, $9$, $12$ и т.д.). Ещё можно как-то разбить $N$ на несколько интервалов, чтобы для первого делителя $3$ перебирать не от $2$, а от числа, сравнимого по порядку с $N/3$.

-- 14.07.2014, 12:11 --

Linkey в сообщении #887347 писал(а):

Наверно в среднем получаются затраты времени $\sqrt{N}$.

Ошибся, пропорционально $N$.

И ещё можно по десятичному или двоичному разложению $N$ сразу определить его порядок, и благодаря этому считать второй делитель не от 2.

[kp9r4d]

Linkey в сообщении #887347 писал(а):

Не понял, что значит “сделать за константу”?

Говоря, что алгоритм работает за $O(1)$ (константу) понимают примерно следующее: вне зависимости от входных данных, алгоритм не сделает операций (или машинных тактов, или чего-нибудь ещё в этом духе) больше, чем некоторая константа $C$. При этом операции сложения, умножения, деления (целочисленного), вычитания и взятия остатка от деления считаются элементарными.
Вот пример задачи: дано число $N$, сколько в наборе $1,2,3,...,N$ чётных чисел?
И два решения:
1) Завести счётчик $x$ перебрать циклом все числа от 1 до $N$ и проверить их чётность, в случае, если число чётное увеличить $x$ на единицу. Этот алгоритм требует $N+N/2$ действий ($N$ взятий остатка от деления и $N/2$ прибавлений в счётчик) то есть, как вы говорите: "пропорционально $N$".
2) Целочисленно поделить $N$ на 2. Этот алгоритм требует одно действие, то есть "пропорционально 1". Или, как говорят ещё "за константу".

Я сформулирую задачу которую вам надо решать: вот есть у вас целые числа $x,z$, и вам надо найти (или сказать, что такового не существует) такое число $y$, при умножении на которое числа $x$ получится число $z$.
Как решить эту задачу без цикла (за константу)?

Linkey в сообщении #887347 писал(а):

но эта задача скорее алгоритмическая, а не математическая.

Это довольно странная дифференциация, легче считать любую задачу, сформулированную формально в математических терминах - математической.

(К слову, вы владеете каким-нибудь языком программирования? Так объяснения будут проще.)

[demolishka]

По первому вопросу гуглить: "тест простоты". По второму: "решето эратосфена и его модификации". А если вам еще понадобится раскладывать число на простые множители, то "алгоритмы факторизации". Ссылки из википедии дадут достаточно информации.

[mishafromusa]

Несколько лет назад был открыт (двумя компьютерщиками из Индии) алгоритм, позволяющий проверить простоту данного числа за время, пропорциональное степени его логарифма, т.е. степени длины числа. Сначала была седьмая с половиной степень, но потом её вроде удалось понизить до шести, точно не помню. http://www.cse.iitk.ac.in/users/manindr ... ity_v6.pdf А вот и по-русски: http://ru.wikipedia.org/wiki/%D0%A2%D0% ... 0%BD%D1%8B

[Linkey]

kp9r4d в сообщении #887357 писал(а):

Целочисленно поделить $N$ на 2. Этот алгоритм требует одно действие, то есть "пропорционально 1". Или, как говорят ещё "за константу".

Я совершенно не помню как нас в школе учили делить столбиком. Чему пропорционально время вычисления по этому алгоритму?
Если я правильно понимаю, когда перемножаешь два числа $N1*N2$ столбиком, время будет пропорционально $Ln(N1*N2)$. Делить столбиком гораздо сложнее, получается что время вычисления будет пропорционально какому-то логарифму, умноженному на N в небольшой степени?

[kp9r4d]

Умножение и деление столбиком работают пропорционально $\ln(N_1+N_2)$, ну это тонкий момент, да. На самом деле, если алгоритмы не работают с очень большими числами (как это и происходит во второй вашей задаче, например), то условно считают, что сложить, умножить или разделить два числа можно за одну операцию.
Я хотел, чтобы вы сказали, что вместо внутреннего цикла можно просто проверять, делится ли нацело одно число на другое (что, как уже договорились, можно сделать за одну операцию) и тогда ваш предложенный алгоритм будет работать за $\sqrt{N}$.

[Linkey]

kp9r4d в сообщении #887397 писал(а):

Умножение и деление столбиком работают пропорционально $\ln(N_1+N_2)$, ну это тонкий момент, да. На самом деле, если алгоритмы не работают с очень большими числами (как это и происходит во второй вашей задаче, например), то условно считают, что сложить, умножить или разделить два числа можно за одну операцию.
Я хотел, чтобы вы сказали, что вместо внутреннего цикла можно просто проверять, делится ли нацело одно число на другое (что, как уже договорились, можно сделать за одну операцию) и тогда ваш предложенный алгоритм будет работать за $\sqrt{N}$.

Я это понял, но ведь делить намного сложнее чем умножать, я думал там будет не только логарифм.

[kp9r4d]

Да нет, вроде не сложнее.

[kp9r4d]

Linkey в сообщении #887405 писал(а):

Умножение и деление столбиком работают пропорционально $\ln(N_1+N_2)$

Прошу прощения. $\ln(N_1)\ln(N_2)$ конечно, то есть пропорционально произведению количества цифр первого числа на количество цифр второго числа. Это если просто столбиком, есть более быстрые методы умножения и деления, вопрос о самом быстром до сих пор стоит.

[VAL]

Linkey в сообщении #887317 писал(а):

1) Задано произвольное число $N$, например гугол плюс $1259$. Нужно определить, является ли оно простым.

С этим можно разобраться за пару секунд в уме.

С другими числами такого же порядка дело обстоит сложнее. Но для современных алгоритмов и компьютеров проверка таких чисел на простоту - не проблема.
При этом применяются методы, не связанные с явным нахождением множителей числа.