Введение Одним из алгоритмов для поиска простых чисел является Решето Эратосфена предложенное еще древнегреческим математиком. Картинка из википедии: Смысл в вычеркивании чисел кратных уже найденным простым. Остающиеся невычеркнутыми в свою очередь являются простыми. Более…
38-летний перуанский математик Харальд Хельфготт три года назад доказал тернарную гипотезу Гольдбаха, а сейчас сумел оптимизировать компьютерный алгоритм для расчёта решета Эратосфена. Фото: Matías Loewy В III в. до нашей эры древнегреческий математик, астроном, географ, филолог и…
В комментариях к одному из прошлых постов о решете Эратосфена был упомянут этот короткий алгоритм из Википедии: Алгоритм 1: 1: для i := 2, 3, 4, ..., до n: 2: если lp[i] = 0: 3: lp[i] := i 4: pr[] += {i} 5: для p из pr пока p ≤ lp[i] и p*i ≤ n: 6: lp[p*i] := p Результат: lp - минимальный простой делитель для кажого числа до n pr -…
Решето Сундарама в сети представлено большим количеством источников краткой справочной информации. Тем не менее, я решил изложить то, что хотел бы прочитать сам в начале изучения теоретико-числовых алгоритмов. Решето Сундарама входит в тройку известнейших методов генерации…