Кто решил проэкт Ейлера 7 задача на PHP?

Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-ое простое число - 13.
Какое число является 10001-ым простым числом?

Насколько я понял искать целое число на 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;
}


print_r( getPrimes(13) ); // проверил все ли работает - работает :)

А дальше тупик :)
$lastel =  end(getPrimes(1000)); // нахожу последний элемент массива при числу меньше 1000

и дальше была мысль
$key = array_search ($lastel, $arr);
echo $key;

Найти что за элемент и вывести его
А вот в обратную сторону голова не варит :)
  • Вопрос задан
  • 1671 просмотр
Пригласить эксперта
Ответы на вопрос 1
MvcBox
@MvcBox
Back-end developer
Вы какую-то фигню нагородили.
Самый простой вариант на JS
(который можно оптимизировать, убрав накопление простых чисел):

'use strict';

const primes = [2, 3, 5, 7, 11, 13];

function isPrime(number) {
    // Получаем лимит для делителя
    const dividersLimit = number / 2;

    // Проверяем делители с шагом 2
    for (let i = 3; i < dividersLimit; i += 2) {
        if (number % i === 0) {
            return false;
        }
    }

    return true;
}

// Начнем поиск, например, с 15 с шагом 2 (так как кроме двойки парных простых чисел больше нет)
for (let i = 15; i < Number.MAX_SAFE_INTEGER; i += 2) {
    if (isPrime(i)) {
        primes.push(i);

        if (primes.length === 10001) {
            console.log('Result:', i);
            break;
        }
    }
}


Результат: 104743
Время выполнения на ноуте примерно 0.4 секунды
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
ЧИТАЙ-ГОРОД Москва
от 140 000 до 210 000 ₽
ЭР-Телеком Пермь
от 80 000 ₽
DANYCOM Краснодар
от 50 000 до 100 000 ₽
06 апр. 2020, в 22:36
10000 руб./за проект
15 мар. 2020, в 17:59
500 руб./в час