Арифметика: простые числа
Тест на простоту. Функция PrimeQ.
Чтобы сказать, является ли простым заданное число из 15 или 20 цифр, не хватит всей жизни, даже если использовать все, что уже известно. | Мерсенн, XVII в.Множество простых чисел Primes и предикат. Доказательство (или опровержение) простоты заданного числа.
Множество простых чисел Primes и предикат х € Primes | В системе Mathematica имеется также множество (область) простых чисел Primes. Его также можно использовать для проверки простоты числа. Нужно просто проверить, принадлежит ли число этому множеству. Убедимся, например, что число 1234567 составное.Функции PreviousPrime и NextPrime и случайные простые числа
В пакете теории чисел (загружается по команде <<NumberTheory'NumberTheory-Functions') имеются две чрезвычайно полезные функции, значениями которых являются простые числа. | Наибольшее простое число, меньшее n, – PreviousPrime[n] | Функция PreviousPrime [n] генерирует наибольшее простое число, меньшее n. Если n не больше 2, будет сгенерировано отрицательное простое число. | PreviousPrime[1]Пифагоровы треугольники, у которых длины двух сторон выражаются простыми числами
Как известно, треугольники, у которых длины двух сторон выражаются целыми числами, называются пифагоровыми. Хорошо известно, что длина ни одной из сторон пифагорового треугольника не может быть равна 2.Таблицы простых чисел
Студент на экзамене: Чтобы составить таблицу простых чисел, нужно трясти решето. | Преподаватель: Сколько раз? | Студент: Ну, пока не вытрясется все лишнее. | Мехматовский фольклор | Функция Prime[n] – n-е простое число рn | В предыдущей главе, разлагая числа на простые множители, мы опустили вопрос о том, как составляются таблицы простых чисел.Поиск отрезков натурального ряда, состоящих только из составных чисел
За одним-единственным исключением pn =2, р2 = 3, числа рn и рn+1 не являются смежными в натуральном ряду. Еще Евклид знал, что существуют сколь угодно длинные отрезки натурального ряда, целиком состоящие из составных чисел.Близнецы
Изучая распределение простых чисел, мы узнали, что интервалы, состоящие из составных чисел, могут быть сколь угодно длинными. Однако встречаются и очень короткие интервалы, ограниченные простыми числами.Простые числа, близкие к числам определенного вида
В ряде областей науки и техники, например в теории кодирования, важно знать простые числа, близкие к числам определенного вида (чаще всего к степеням таких оснований, как 2, 3 и 10). Вне сомнения, их можно было бы найти в обычных таблицах простых чисел.Число простых чисел, не превосходящих х
Функция PrimePi[x] | Согласитесь, изучив все тонкости искусства составления таблиц простых чисел, было бы нелогично пренебречь искусством составления таблиц на основе уже созданных. Почему бы, имея полную (значит, бесконечную!) таблицу простых чисел, не поинтересоваться, сколько чисел в этой таблице не превосходят данного числа х. Иными словами, определить число простых чисел, не превосходящих х.Количество простых чисел на открытом слева отрезке (а, b]
С помощью функции PrimePi несложно подсчитать и количество простых чисел на открытом слева отрезке (а, b]. Помните только, что если вы пользуетесь выражением k(b)-n(а), т.е. выражением PrimePi [b] – PrimePi [a], то в случае простоты простое число b будет посчитано, а простое число а – нет.