Теория чисел
Решето Эратосфена, НОД и НОК по алгоритму Евклида и разложение на простые множители — с пошаговым решением. Полезно для алгоритмов и олимпиад. Считается прямо в браузере.
Решето Эратосфена
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
Простых чисел: 25
НОД и НОК (алгоритм Евклида)
НОД(48, 36) = 12 · НОК = 144
| a | b | a = b·q + r |
|---|---|---|
| 48 | 36 | 48 = 36·1 + 12 |
| 36 | 12 | 36 = 12·3 + 0 |
Разложение на простые множители
360 = 23 · 32 · 5
О теории чисел
Решето Эратосфена находит все простые числа до N, вычёркивая кратные каждого найденного простого. Алгоритм Евклида ищет НОД, заменяя бо́льшее число остатком от деления, пока он не станет нулём; НОК получается как a·b / НОД. Любое число единственным образом раскладывается в произведение простых — это основная теорема арифметики. Эти операции — база для криптографии, дробей и многих алгоритмов.
