Вычисление простых чисел программирование

Алгоритмы поиска простых чисел в C#

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

Простое число — это целое положительное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Определение того является ли число простым или нет — это одна из самых распространенных задач, решаемых в рамках курса лабораторных работ по информатике. Ниже будет представлена реализация алгоритма поиска простых чисел в C#, а также использование различных циклов для вывода простых чисел.

Задача №1

Проверить является ли число простым и вывести результат вычисления в консоль.

Алгоритм определения простого числа

Для того, чтобы проверить является ли число N простым необходимо:

1. Задаем значение N
2. Задаем цикл for от 2 до N-1 (счётчик цикла обозначим, например, как i )
   1. Если остаток от деление N на i равен нулю, то число не является простым — выходим из цикла
   2. Если остаток от деления N на i не равен нулю, то переходим к следующей итерации цикла

   Реализация алгоритма определения простого числа в C#

   Метод определения простого числа в C#, реализующий представленный выше алгоритм может быть представлен следующим образом:

   public bool IsPrime(int number) < for (int i = 2; i < number; i++) < if (number % i == 0) return false; >return true; >

   Пример определения простых чисел из диапазона от 1 до N

   Если по условиям задачи конечное значение диапазона задается в виде числа N , то здесь удобно использовать цикл for или while. Пример программы с использованием цикла for представлен ниже:

   using System; namespace Prime < class Program < public static bool IsPrime(int number) < for (int i = 2; i < number; i++) < if (number % i == 0) return false; >return true; > static void Main(string[] args) < Console.WriteLine("Введите конечное значение диапазона 1. N и нажмите Enter"); Console.WriteLine("N = "); if ((!int.TryParse(Console.ReadLine(), out int result))||(result<0)) Console.WriteLine("Число должно быть положительным и целым"); Console.WriteLine($"Простые числа из диапазона от 1 до "); int count = 0; for (int i = 1; i "); count++; > > Console.WriteLine(""); Console.WriteLine($"Найдено простых чисел из диапазона от 1 до "); > > >

   Строго говоря, число 1 не является ни простым не составным, поэтому его можно было бы исключить из цикла, что мы и сделаем в следующем примере.

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

   Задача поиска простых чисел может быть сформулирована и по другому, например, так: найти первые N простых чисел. В этом случае нам будет выгодно использовать цикл while:

   using System; namespace Prime < class Program < public static bool IsPrime(int number) < for (int i = 2; i < number; i++) < if (number % i == 0) return false; >return true; > static void Main(string[] args) < Console.WriteLine("Введите количество простых чисел которые необходимо найти"); Console.WriteLine("N = "); if ((!int.TryParse(Console.ReadLine(), out int result))||(result<=0)) Console.WriteLine("Число должно быть положительным и целым"); Console.WriteLine($"Первые простых чисел"); int count = 0; //количество найденных простых чисел int number = 1; //очередное число, проверку которого необходимо найти int total = 0; //общее количество проверенных чисел while (count "); count++; > > Console.WriteLine(""); Console.WriteLine($"Найдено простых чисел. Проверено чисел"); > > >

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

   Итого

   Сегодня мы рассмотрели алгоритм поиска простых чисел и реализовали этот алгоритм в C#. В зависимости от условий задачи, мы использовали различные виды циклов для поиска набора простых чисел.

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

   Источник

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

   Программа принимает на вход число и проверяет, простое оно или нет.

   Решение задачи

   1. Принимаем на вход число и записываем его в отдельную переменную.
   2. Инициализируем переменную, которая будет выполнять роль счетчика, значением 0 .
   3. Организуем цикл for в диапазоне от 2 до значения проверяемого числа, деленного на 2 (речь идет, конечно, о целочисленном делении).
   4. Затем находим количество делителей нашего числа. При помощи условного оператора if мы проверяем, делится ли число без остатка, и затем, если делится, увеличиваем наш счетчик на единицу.
   5. Если число делителей равно 0 , то проверяемое число является простым.
   6. Выводим результат на экран.
   7. Конец.

   Исходный код

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

   a = int(input("Введите число: ")) k = 0 for i in range(2, a // 2+1): if (a % i == 0): k = k+1 if (k 
   Объяснение работы программы
   
     
   Пользователь вводит число, и оно сохраняется в переменную a .
     
   Инициализируем переменную k значением 0 . Эта переменная будет выполнять роль счетчика.
     
   Запускаем цикл for в диапазоне от 2 до значения проверяемого числа, деленного на 2 (речь идет, конечно, о целочисленном делении). Напоминаем, что само число и 1 делителями мы считать не будем.
     
   Затем, при помощи инструкции if , на каждой итерации цикла мы проверяем, делится ли наше число без остатка на числа из выбранного диапазона цикла. Если делится, то переменная k , выполняющая роль счетчика, увеличивается на единицу.
     
   Если число делителей равно 0 , то проверяемое число является простым.
     
   Выводим полученный результат на экран.
   
   Результаты работы программы
   Пример 1: Введите число: 7 Число простое Пример 2: Введите число: 35 Число не является простым
    
   Еще более 50 задач на числа в нашем телеграм канале Python Turbo. Уютное сообщество Python разработчиков.
    
   Источник
    
   Вычисление простых чисел программирование
    
   Наиболее наивный подход к поиску простых чисел заключается в следующем. Будем брать по очереди натуральные числа n , начиная с двойки, и проверять их на простоту. Проверка на простоту заключается в следующем: перебирая числа k из диапазона от 2 до n − 1 , будем делить n на k с остатком. Если при каком-то k обнаружится нулевой остаток, значит, n делится на k нацело, и число n составное. Если же при делении обнаруживались только ненулевые остатки, значит, число простое; в этом случае выводим его на экран. Ясно, что, получив нулевой остаток (тем самым обнаружив, что n составное), следует отказаться от дальнейших проб на делимость.
    
   Заметим, что все простые числа, за исключением двойки, нечётные. Если обработать особо случай n = 2 , то все последующие числа n можно перебирать с шагом 2 . Это даст приблизительно двукратное увеличение производительности программы.
    
   Оптимизированный перебор делителей
    
   Ещё одно улучшение возникает благодаря следующему утверждению: наименьший делитель составного числа n не превосходит n . Докажем это утверждение от противного. Пускай число k является наименьшим делителем n , причём k > n . Тогда n = k ⁢ l , где l ∈ ℕ , причём l ⩽ n , то есть l также является делителем числа n , кроме того, меньшим, чем k , а это противоречит предположению. Всё это означает, что, перебирая потенциальные делители, можно оборвать перебор, когда k достигнет n : если до этого момента делителей не найдено, то их нет вообще. Кстати, при проверке на простоту числа 11 это наблюдение позволяет сократить перебор более чем в три раза, а для числа 1111111111111111111 — более чем в 1054092553 раза (оба числа — простые).
    
   Перебор с запоминанием найденных простых чисел
    
   Существенно сократить перебор возможных делителей можно, пожертвовав памятью во время исполнения программы. В основе этой оптимизации лежит следующее утверждение: наименьший собственный делитель k составного числа n (то есть отличный от единицы и от самого n ) является простым. Докажите самостоятельно.
    
   Поскольку при проверке числа n на простоту важен именно наименьший собственный делитель, делители следует искать среди простых чисел, перебирая их по порядку. Но где взять их список? Ответ прост: поскольку наша программа будет искать все простые числа по порядку, кроме вывода на экран будем добавлять их в список найденных простых. Для очередного n будем перебирать потенциальные делители только из этого списка, по-прежнему, вплоть до n .
    
   Издержкой этого подхода является необходимость держать в памяти растущий список найденных простых чисел. Однако объём требуемой для этого памяти будет невелик по сравнению с громадным выигрышем в быстродействии. Следующая таблица даёт представление об экономии при переборе и о затратах памяти:
    
    
    
   n
    
   количество k ⩽ n
    
   количество простых k ⩽ n
    
     
    
    
   10
    
   3
    
   1
    
    
    
   100
    
   10
    
   4
    
    
    
   1000
    
   31
    
   10
    
    
    
   10000
    
   100
    
   25
    
    
    
   100000
    
   316
    
   65
    
    
    
   1000000
    
   1000
    
   168
    
    
    
    
   Решето Эратосфена
    
   Другой алгоритм поиска простых чисел приписывают древнегреческому учёному Эратосфену Киренскому (Έρατοσθένης).
    
   Обратите внимание: количество зачёркиваний у составного числа — это количество простых делителей (без учёта кратности).
    
   Колёсный метод
    
   Трюк, упомянутый в разделе «Наивный перебор», позволяет вдвое сократить список кандидатов в простые числа — заведомо составными будут все чётные числа кроме двойки. Посмотрим, нельзя ли подобным образом учесть ещё несколько первых простых чисел, чтобы дополнительно уменьшить число кандидатов.
    
   Чисел, делящихся на 2 — половина, а делящихся на 3 — треть. Значит, доля чисел, делящихся хотя бы на одно из этих чисел, равна 1 2 + 1 3 − 1 2 ⋅ 1 3 = 2 3 (вычитается доля чисел, делящихся и на 2 , и на 3 , иначе такие числа будут учтены дважды). Для интересной операции, которую мы только что выполнили над дробями 1 2 и 1 3 , введём обозначение: x ⊕ y = x + y − x ⁢ y .
    
   Очевидно, операция ⊕ коммутативна: x ⊕ y = y ⊕ x . Кроме того, как нетрудно проверить, она ассоциативна: x ⊕ y ⊕ z = x ⊕ y ⊕ z .
    
   Теперь ясно, что учёт следующего простого числа, пятёрки, увеличивает долю заведомо составных чисел (делящихся на 2 , 3 , 5 ) до 1 2 ⊕ 1 3 ⊕ 1 5 = 11 15 . Учёт семёрки даст 1 2 ⊕ 1 3 ⊕ 1 5 ⊕ 1 7 = 11 15 ⊕ 1 7 = 27 35 . Интересно выяснить, какую выгоду можно получить, учитывая следующие простые числа, и каковы будут издержки.
    
   Мы вычислили «суммы» обратных величин для первых k простых чисел и свели результаты в таблицу:
    
    
    
   k
    
   1 2 ⊕ 1 3 ⊕ 1 5 ⊕ … ⊕ 1 p k
    
     
    
    
   1
    
   0,5000…
    
    
    
   2
    
   0,6667…
    
    
    
   3
    
   0,7333…
    
    
    
   4
    
   0,7714…
    
    
    
   5
    
   0,7922…
    
    
    
   6
    
   0,8082…
    
    
    
   7
    
   0,8195…
    
    
    
   8
    
   0,8290…
    
    
    
   9
    
   0,8364…
    
    
    
   10
    
   0,8421…
    
    
    
    
   Числа в правой колонке таблицы растут, но всё медленней.
    
   Список чисел от 1 до P k , взаимно простых с P k , назовём колесом, а сами такие числа — спицами в колесе. Теперь мы знаем, что любое из простых чисел либо одно из p 1 , p 2 , … , p k , либо содержится среди чисел вида s + n ⁢ P k , где s — спица. Все остальные натуральные числа, кроме единицы, заведомо составные, и их доля, как показывает таблица, довольно велика даже для небольших k .
    
   Для проверки числа N на простоту следует прежде всего поискать N среди чисел p 1 , p 2 , … , p k . Если поиск не увенчался успехом, проверяем по очереди, не делится ли N на одно из p i . Если делится, число N — составное. Если же нет, ищем делители N среди спиц колеса s (пропустив, естественно, единицу), затем среди чисел вида s + P k , затем среди чисел вида s + 2 ⁢ P k , затем — s + 3 ⁢ P k , и так продолжаем до тех пор, пока квадрат очередного делителя не превысит N .
    
   Построим колёса для первого одного простого числа, первых двух и первых трёх:
    
    
    
   k
    
   колесо
    
     
    
    
   1
    
   1
    
    
    
   2
    
   1 , 5
    
    
    
   3
    
   1 , 7 , 11 , 13 , 17 , 19 , 23 , 29
    
    
    
   4
    
   1 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , 103 , 107 , 109 , 113 , 121 , 127 , 131 , 137 , 139 , 143 , 149 , 151 , 157 , 163 , 167 , 169 , 173 , 179 , 181 , 187 , 191 , 193 , 197 , 199 , 209
    
    
    
    
   Возьмём для примера колесо, построенное для двух первых простых чисел — 2 и 3 . Проверяя на простоту число N при помощи такого колеса, убедившись, что N не двойка и не тройка, пытаемся делить это число сначала на 2 , 3 , а затем — на 5 , 7 , 11 , 13 , 17 , 19 , 23 , 25 , 29 , … , то есть на числа из арифметических прогрессий 1 + 6 ⁢ t и 5 + 6 ⁢ t , t = 0 1 2 3 … . При N = 661 имеет смысл остановиться на числе 25 , поскольку квадрат следующего в списке, 29 , уже больше 661 . Теперь можно заключить, что число 661 — простое.
    
   Удобно изображать список возможных делителей в виде таблицы шириной P k (в нашем примере это 2 ⋅ 3 = 6 ): 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 … Серые числа заведомо составные. Среди цветных чисел также могут встретиться, хоть и редко, составные числа (синие) — мы помним, что колёсный метод исключает не все составные числа из рассмотрения.
    
   Для проверки того же числа 661 на колесе, построенном для трёх первых простых чисел, нужно проверить его делимость сначала на 2 , 3 , 5 , затем — на 7 , 11 , 13 , 17 , 19 , 23 .
    
   Есть соблазн использовать для построения колеса как можно больше первых простых чисел. Но не стоит этого делать. Выигрыш с добавлением очередного простого числа будет всё меньше и меньше, а количество спиц в k -ом колесе будет расти всё быстрее и быстрее. Можно показать, что количество спиц в k -ом колесе равно p 1 − 1 ⁢ p 2 − 1 ⁢ p 3 − 1 ⋅ … ⋅ p k − 1 . Эта последовательность выглядит так: 1 , 2 , 8 , 48 , 480 , 5760 , 92160 , 1658880 , … . Слишком большие колёса только замедлят выполнение программы, к тому же создание списка спиц потребует массу времени. Наши эксперименты показали, что оптимальное количество простых, используемых для построения колеса, равно четырём.
    
   Ах, да. Почему метод называется колёсным? Возьмём колесо со спицами, пронумерованными от 1 до P k , и удалим спицы с номерами, не взаимно простыми с P k . Если прокатить такое колесо по прямой, отмечая следы концов уцелевших спиц, на прямой останутся отметки, принадлежащие арифметическим прогрессиям вида s + P k ⁢ t . Первые три колеса показаны на рисунке 14.1. «Колёса для проверки чисел на простоту». Следующее колесо уже в семь раз больше самого крупного из показанных, и мы решили воздержаться от его рисования.
    
   Источник
    
   Читайте также:  Изучаем язык программирования pascal