От одной из компаний получил тестовое задание, которое выполнено, по словам специалистов компании, самым простым способом. Считаю полезным рассмотреть и пояснить выполнение задачи.
Описание задачи:
Задача показалась стандартной и пробежался по Интернету, чтобы найти варианты ее решения, которые могут предложить другие программисты.
Увидел разные варианты, от решения "в лоб" - перебор всех чисел от 1 до заданного с проверкой целого деления, до несколько экстравагантных, с созданием объекта класса и обработки функционала через методы (хотя осуществлялся тот же самый перебор " в лоб").
Но, как оказалось, в написании своей функции уже давно нет необходимости. Математический аппарат PHP очень хорошо развит, и в языке присутствует функция, которая позволяет определять является ли число простым. Эта функция gmp_prob_prime.
Алгоритм функции построен на тесте Миллера-Рабина, который является расширением теста Ферма, и позволяет с высокой степенью вероятности определять составные числа.
Результат проверки числа данной функцией может быть 0 - число не является простым однозначно, 1- число возможно простое, 2 - число точно простое.
Есть и другие методы (тесты) для определения является ли число простым, но сейчас этот вариант вероятно более привлекателен по результативности и скорости обработки.
Вот такой результат решения задачи получился:
