Задача 1 (1). Дано натуральное число n. Определить, является ли оно простым.

1.1. Постановка задачи. Натуральное число, большее единицы, называется простым, если имеет только два натуральных делителя – единицу и самого себя. Иначе число называется составным. Отнесение единицы к простым или составным обычно требует дополнительного соглашения. Мы будем считать единицу составным числом.

Определение простоты числа является одной из важнейших задач математики (точнее теории чисел). Кроме того, эта задача важна и с практической точки зрения, так как большинство современных криптографических алгоритмов использует большие простые числа как некоторые параметры.

Естественно, для определения простоты числа применительно к достаточно большим числам применяются специальные алгоритмы. Более того, в таком случае применяются не только так называемые детерминированные алгоритмы, но и вероятностные, определяющие простоту числа при заданном уровне вероятности. В свою очередь, применение таких алгоритмов для тестирования относительно небольших натуральных чисел бессмысленно. В этом случае часто используется простой перебор делителей. Мы реализуем именно этот метод.

1.2. Алгоритм. Изобразим алгоритм в виде блок–схемы.

1.3. Текст программы (C++). Программу напишем на компилируемом языке С++:

#include <iostream>

#include <math.h>

#include <assert.h>

static bool is_prime(const int n) {if (n == 1)

return false;

for (int i = 2; i <= (int)sqrt(n); i++) {if (n % i == 0) return false;}

return true;}

int main() {std::cout << "Проверка простоты числа." << std::endl;

std::cout << "Введите натуральное число: "; int a;

std::cin >> a; assert(a > 0);

std::cout << "Число " << a << " - "

<< ((is_prime(a) ? "простое" : "составное")) << std::endl;

return 0;}

Естественно, алгоритм из блок–схемы реализован в программе не буквально, а с учётом особенностей и традиций языка C++. Кроме того, чтобы не усложнять программу, мы не делаем явную проверку натуральности числа a. Вместо этого мы используем assert для проверки допустимости аргумента, который обычно используется программистами при отладке программ.

1.4. Результат работы программы (C++).

Компиляция на операционной системе Ubuntu 12.04 компилятором gcc

4.8.1:

$ g++ -o prime ./prime.cpp

Проверка числа 131071, одного из простых чисел Мерсенна.

$ ./prime

Проверка простоты числа.

Введите натуральное число: 131071 Число 131071 – простое

Проверка число 123, которое очевидно делится на 3.

$ ./prime

Проверка простоты числа.

Введите натуральное число: 123 Число 123 – составное.

1.5. Текст программы (Python). Приведём текст программы, написанной на популярном интерпретируемом языке Python. В данном случае приведён Bash- скрипт для выполнения его в Unix-среде:

#!/usr/bin/env python

import math

def is_prime(n):

return False if n == 0 else not any(n % i == 0 for i in range(2, int(math.sqrt(n)) +1))

if name == " main ":

print "Primality test." try:

a = int(input('Enter natural number: ')) assert(a > 0)

print "Nunber {0} is ".format(str(a)) + ("prime" if is_prime(a) else "compo­site")

except Exception as e:

print "Error: {0}".format(str(e))

В данном случае, для Python-а мы сделали вывод всех сообщений на ан­глийском языке.