Полезен ли алгоритм определения НЕпростоты числа с 3 операций? Изучал одну теорию, оказалось она верна в 75-80% случаев. То есть для любого числа с вероятностью в 75% алгоритм говорит, что оно не простое, при этом совершается всего 3 математических операции, никаких циклов и т.п. Алгоритм остается с такой же вероятностью верным при любом числе знаков, проверял в очень широком диапозоне. Может ускорить другие алгоритмы проверки на простоту, то есть прежде чем проверять сложными алгоритмами можно прогнать этим и с 75% сказать что число не простое и дальше не проверять. Вопрос, нужно такое чудо кому ни будь или с такой погрешностью с него толку нет?
Алгоритм простой, есть определенные числа, при деления на которые остаток от деления будет простым числов в 75% случаев, поэтому если остаток от деления оказался не простым числом можно считать, что оно составное.class MayBePrime
{
static bool[] charr = null;
static int prime = 30030;//30030 для быстрого старта, ниже точность. Произведение первых простых чисел
static public bool isMayBePrime(System.Numerics.BigInteger x)
{
if (charr == null)
{
charr = new bool[prime];
for (int i = 0; i
Полезен ли алгоритм определения НЕпростоты числа с 3 операций? Изучал одну теорию, оказалось она верна в 75-80% случаев. То есть для любого числа с вероятностью в 75% алгоритм говорит, что оно не простое, при этом совершается всего 3 математических операции, никаких циклов и т.п. Алгоритм остается с такой же вероятностью верным при любом числе знаков, проверял в очень широком диапозоне. Может ускорить другие алгоритмы проверки на простоту, то есть прежде чем проверять сложными алгоритмами можно прогнать этим и с 75% сказать что число не простое и дальше не проверять. Вопрос, нужно такое чудо кому ни будь или с такой погрешностью с него толку нет?
Алгоритм простой, есть определенные числа, при деления на которые остаток от деления будет простым числов в 75% случаев, поэтому если остаток от деления оказался не простым числом можно считать, что оно составное.class MayBePrime
{
static bool[] charr = null;
static int prime = 30030;//30030 для быстрого старта, ниже точность. Произведение первых простых чисел
static public bool isMayBePrime(System.Numerics.BigInteger x)
{
if (charr == null)
{
charr = new bool[prime];
for (int i = 0; i
Алгоритм простой, есть определенные числа, при деления на которые остаток от деления будет простым числов в 75% случаев, поэтому если остаток от деления оказался не простым числом можно считать, что оно составное.class MayBePrime
{
static bool[] charr = null;
static int prime = 30030;//30030 для быстрого старта, ниже точность. Произведение первых простых чисел
static public bool isMayBePrime(System.Numerics.BigInteger x)
{
if (charr == null)
{
charr = new bool[prime];
for (int i = 0; i
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Этот алгоритм определения НЕпростоты числа с использованием остатков от деления на определенные числа может быть полезен в определенных случаях, но имеет свои ограничения.
С точки зрения эффективности, он может быть использован как первый быстрый этап проверки на простоту, чтобы исключить большую часть составных чисел с вероятностью 75%. Это может ускорить более сложные алгоритмы для проверки простоты, такие как тест Миллера-Рабина или тест Соловея-Штрассена.
Однако стоит помнить, что вероятность ошибки в 25% все еще существует, что означает, что некоторые простые числа могут быть неверно определены как составные. Поэтому в зависимости от конкретной ситуации, возможно, будет необходимо дополнительно проверять числа с помощью более надежных алгоритмов.
Таким образом, данный алгоритм может быть полезен как первый этап в проверке на простоту, чтобы ускорить процесс, но его использование должно быть сбалансировано с учетом вероятности ошибок в результате.