Иллюстрированный самоучитель по Mathematica 5

Тест на простоту. Функция PrimeQ.

Упражнение 5.2.
Найдите все простые числа, записываемые не более чем N единицами. Иными словами, составьте список всех натуральных n<N, для которых является простым число, состоящее из и единиц. Рассмотрите случай N = 5000.

Решение.
Достаточно ввести в блокнот следующую программу.

Однако время выполнения программы можно сократить, если вспомнить, что число данного вида может быть простым, только если п простое. Тогда программа несколько усложнится.

В результате счета по этой программе будут выведены следующие числа:

Упражнение 5.3.
Составьте список всех натуральных n<N, для которых является простым число вида 10ⁿ +1 = 1000……………………….00001 (n-1 нулей в середине), состоящее из n+1 цифр. Рассмотрите случай N -131071 = 2¹⁷ -1.

Решение.
Такие числа могут быть простыми лишь в том случае, если п является степенью двойки, т.е. если n = 2^k. (При нечетных п, все такие числа делятся, например, на сумму оснований, т.е. на П.) Учитывая это, цикл можно вести лишь По показателям степеней двойки. Печатать нужно лишь те степени двойки, при которых рассматриваемое число оказывается простым. Предельное значение, при котором можно остановить цикл, равно наибольшему k, при котором 2* £N. Однако нужно учесть случай k = 0. Тогда программа будет выглядеть так.

В результате счета по этой программе будет выведено только два числа:

Упражнение 5.4.
Найдите номера простых чисел Фибоначчи, не превышающие N. Иными словами, нужно составить список всех натуральных r&N, для которых число Фибоначчи F_n является простым. Рассмотрите случай N=25 000.

Решение. Такие числа могут быть простыми лишь в том случае, если n является простым числом или n= 4. Поэтому цикл можно вести лишь по простым числам, учитывая, конечно, исключение n = 4. Печатать нужно лишь те n, при которых число Фибоначчи F_n оказывается простым. Вот как может выглядеть программа.

В результате прогона этой программы будут выведены только следующие числа:

Как видите, таких чисел совсем немного. В 1963 году наибольшим известным из этих чисел было только 47, которому отвечало всего лишь десятизначное число Фибоначчи.

Упражнение 5.5.
Среди факториалов есть только одно простое число: 2 = 21. Найдите все такие натуральные n, не превышающие N, что n!-1 – простое. Иными словами, нужно составить список всех натуральных n<N, для которых число n!-1 является простым. Рассмотрите случай N = 1 000.

Решение.
Вот как может выглядеть программа.

Казалось бы, ничего необычного, однако обратите внимание на пробел между знаком минус - и единицей 1. Если вы его не введете, программа будет синтаксически верной, но n! и -1 просто перемножатся, и вы фактически будете искать простые числа среди факториалов.

В результате прогона этой программы будут выведены следующие числа:

Упражнение 5.6.
Найдите все такие натуральные n, не превышающие N, что n!+1 – простое. Иными словами, нужно составить список всех натуральных n>N, для которых число л!+1 является простым. Рассмотрите случай N= 1 000.

Решение.
Вот как может выглядеть программа.

В результате прогона этой программы будут выведены следующие числа:

Как видите, таких чисел совсем немного.