Поиск простых чисел на PHP

Простые числа — это натуральные числа больше 1, которые делятся только сами на себя или на 1. Часто возникающая (например, при шифровании данных) задача — найти все простые числа от 2 до заданного N. Для этого придумано несколько алгоритмов разной эффективности. Давайте рассмотрим их реализацию на PHP.

Простой перебор делителей

Это простейший и наименее эффективный алгоритм из рассмотренных. Для небольших чисел, однако, он вполне применим.

Суть алгоритма: мы просто последовательно перебираем все числа от 2 до N и проверяем, простые они, или нет. Функция проверки на простоту перебирает все нечетные числа от 2 до квадратного корня из N и, если находит такое, на которое N делится без остатка, то число считается составным, а если не находит, то простым.

<?php
function isPrime($number)
{
        if ($number==2)
                return true;
	if ($number%2==0)
		return false;
	$i=3;
	$max_factor = (int)sqrt($number);
	while ($i<=$max_factor){
		if ($number%$i == 0)
			return false;
		$i+=2;
	}
	return true;
}

function getPrimes($max_number)
{
	$primes = [];
	for ($i=3; $i<=$max_number; $i++){
		if (isPrime($i))
			$primes[] = $i;
	}
	return $primes;
}

Эффективность такого алгоритма: O(n * sqrt(n))

Решето Эратосфена

Этот алгоритм как бы «просеивает» все числа от 0 до максимального N через условное решето несколько раз. Сначала последовательно исключаются все числа, кратные 2. Само число добавляется в массив простых чисел. Далее из оставшихся исключаются все числа, кратные следующему простому числу — трем. 4 уже было удалено из исходного массива, соответственно, следом удаляются все числа, кратные 5, и так далее, пока не будут перебраны все числа.

Вот пример решета Эратосфена на PHP:

<?php
function getPrimes($max_number)
{
	$primes = [];
	$is_composite = [];
	for ($i=4; $i<=$max_number; $i+=2){
		$is_composite[$i] = true;	
	}
	$next_prime = 3;
	while ($next_prime<=(int)sqrt($max_number)){
		for ($i=$next_prime*2; $i<=$max_number; $i+=$next_prime){
			$is_composite[$i] = true;	
		}
		$next_prime += 2;
		while ($next_prime<=$max_number && isset($is_composite[$next_prime])){
			$next_prime+=2;	
		}
	}
	for ($i=2; $i<=$max_number; $i++){
			if (!isset($is_composite[$i]))
				$primes[] = $i;
		}
	return $primes;
}

Такой алгоритм имеет эффективность O(n * log(log n)) .

Метод нахождения псевдопростых чисел с использованием теста простоты Ферма

Данный метод позволяет находить простые числа гораздо быстрее предыдущих двух, однако, это будут псевдопростые числа, то есть числа, которые являются простыми лишь с некоторой (тем не менее, очень высокой, около 100%) вероятностью.

Здесь используется тест Ферма, который гласит: если p-простое число, то если возвести число n в степень (p-1), а потом взять результат возведения в степень по модулю p (остаток от деления на p), то в итоге получится 1.

Проблема в том, что если p не является простым, то есть вероятность, что в результате описанных вычислений вы все равно получите 1. Тогда n называется обманщиком Ферма, а если результат не равен 1, то число n называют свидетелем Ферма, так как оно верно указывает на составную природу тестируемого числа p. Вероятность того, что выбранное произвольно для теста число n окажется свидетелем Ферма 50%. Это, конечно, лишает смысла одиночный тест на простоту, но если провести несколько тестов с разными n, то вероятность можно многократно увеличить до приемлемых величин. Скажем, 10 последовательных тестов с разными n, которые выдали, что число является простым, дадут вероятность того, что число все же было составным, всего в 0.00098. 100 тестов и вовсе дадут число, кратное десяти в степени -31. Для практического применения такой низкой вероятности ошибки вполне достаточно.

Вот реализация поиска простых чисел с использованием теста Ферма на PHP:

<?php
function isPrimeByFerma($number, $max_tests)
{
	for ($i=1; $i<=$max_tests; $i++){
		$n = mt_rand (1, $number-1);
		if (($n**($number-1))%$number != 1)
			return false;
	}
	// probability of the number being prime is 1/2^max_tests
	return true;
}


function getPrimes($max_number, $max_tests)
{
	$primes = [];
	for ($i=2; $i<=$max_number; $i++){
		if (isPrimeByFerma($i, $max_tests))
			$primes[] = $i;
	}
	return $primes;
}

Эффективность такого алгоритма O(n * log²n * log (log n) * log (log (log n)))

Кроме указанных алгоритмов существуют и такие, как:

Решето Сундарама

Решето Аткина

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