Кто решил проэкт Ейлера 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;

Найти что за элемент и вывести его
А вот в обратную сторону голова не варит :)
  • Вопрос задан
  • 1556 просмотров
Пригласить эксперта
Ответы на вопрос 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 секунды
Ответ написан
Ваш ответ на вопрос

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

Войти через центр авторизации
Похожие вопросы
Алгоритмика Москва
от 110 000 до 160 000 руб.
N1.RU Новосибирск
от 100 000 руб.
Living Core Казань
от 50 000 руб.
16 сент. 2019, в 16:51
10000 руб./за проект
16 сент. 2019, в 16:47
25000 руб./за проект
16 сент. 2019, в 16:31
5000 руб./за проект