10001-ое простое число
Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-ое простое число – 13.
Какое число является 10001-ым простым числом?
Эту задачу можно решить простым перебором. Для начала создадим функцию, которая будет проверять, являются ли числа простыми:
def is_simple(number):
for i in range(2, number):
if number % i == 0:
return False
return True
Теперь соберём итоговый код, который будет перебирать все простые числа. Выборка будет с шагом 2 и началом в числе 3, потому что чётные числа больше двойки, очевидно, не будут простыми.
simple_numbers_count = 2 # Учитываем, что 2 и 3 – простые числа
# (проверка начнётся с 5)
i = 3
while simple_numbers_count < 10001:
i += 2
if is_simple(i):
simple_numbers_count += 1
print(i)
# Output: 104743Когда уже дописал это решение, захотел погуглить, как можно ускорить проверку чисел на делимость (сначала делаю, потом думаю, ага), и наткнулся на этот пост с Хабра: https://habr.com/ru/post/122538/Основная мысль автора в том, что делители числа всегда существуют попарно. Например, 6 = 2*3, то есть, если мы нашли наименьший из делителей, то не обязательно прочёсывать дальше, чтобы найти его пару. Наибольшим наименьший делитель является в случае, когда эти делители равны (и равны квадратному корню из данного числа). Поэтому имеет смысл проверять только числа в диапазоне до квадратного корня из данного числа.Теперь итоговый код компилируется менее, чем за секунду (вместо 1,5 минут) и выглядит так:
def is_simple(number):
for i in range(2, int(number**0.5)+1):
if number % i == 0:
return False
return True
simple_numbers_count = 2
i = 3
while simple_numbers_count < 10001:
i += 2
if is_simple(i):
simple_numbers_count += 1
print(i)
Задача №7 10001-ое простое число
Условие задачи
Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, что 6-ое простое число – 13.
Какое число является 10001-ым простым числом?
Принцип ее решения очень похож на Задачу 3 (наибольший простой делитель), но ограничением будет выступать не само число, а количество чисел в словаре.
Решение
Для начала определим функцию определения простого числа:
def issimple(n):
r=math.ceil(math.sqrt(n))
for i in range(2,n):
if n%i==0:
return False
return True
Здесь аналогично задаче 3 – для оптимизации перебираем числа до квадратного корня искомого числа. Если n делится на хотя бы одно число от 2-х до корня n возвращаем false. Иначе True
Приведу полный оптимизированный текст:
import math
def issimple(n):
r=math.ceil(math.sqrt(n))
for i in range(2,n):
if n%i==0:
return False
return True
n=5
s=[2,3]
while True:
if issimple(n) is True:
s.append(n)
if len(s)==10001:
break
n+=2
print(s[-1])
Не смотря на все попытки дальнейшей оптимизации цикл выполняется чуть меньше 3-х минут.
Основные принципы оптимизации: перебираем начиная с 5-ти и увеличиваем на 2 (чтобы не включать четные числа.
Условием выхода из цикла является длина списка = 10001
Если у вас получится выполнить задачу более оптимально рад услышать ваши предложения.
Популярные сообщения из этого блога
. Задача №1 Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел – 23. Найдите сумму всех чисел меньше 1000, кратных 3 или 5. Решение
Условие задачи Простые делители числа 13195 – это 5, 7, 13 и 29. Каков самый большой делитель числа 600851475143, являющийся простым числом? Решение Простым числом, является натуральное число больше единицы, которое имеет 2 делителя – 1 и само себя. Для начала найдем все простые делители необходимого числа. Чтобы сократить поиск будем перебирать до квадратного корня 600851475143 округленного вверх ( функцией math.ceil) Перебор будем вести начиная с числа 3. Если i делит число на цело, рекурсивно обращаемся к функции issimple c аргументом i. Функция issimple возвращает пустой список если число является простым. В этом случае число попадает в результирующий список Далее остается только вернуть максимальное значение массива простых чисел, которые нацело делят число 600851475143 Код Python import math def issimple(a): r=math.ceil(math.sqrt(a)) lst=[] for i in range(3,r): if a%i==0: if issimple(i)==[]: lst.app
Условие задачи 2520 – самое маленькое число, которое делится без остатка на все числа от 1 до 10. Какое самое маленькое число делится нацело на все числа от 1 до 20? Скажу сразу – не смотря на не большой диапазон чисел условия реализация этой задачи получилась громоздкой и ее выполнение занимает больше всего времени – около 90 с несмотря на все попытки оптимизации. Решение
$begingroup$
I’m helping my son with Project Euler and we’re working on problem 7, “What is the 10001st prime number?” We’ll use a Sieve of Eratosthenes and we’ll increase the size of the initial array until we’re left with 10001 primes. We’ll start with a pretty big array and increase it by whatever seems reasonable, since there is no time constraint, until we get the answer.
My question is, is there a way to make an informed guess about the size of the initial array?
asked Jun 19, 2011 at 12:32
$endgroup$
$begingroup$
Wikipedia gives the bounds $n ln n + n(lnln n – 1) < p_n < n ln n + n ln ln n$, where $p_n$ is the $n$th prime. So the $10001$st prime is between 104318 and 114320.
answered Jun 19, 2011 at 12:41
Chris EagleChris Eagle
32.7k2 gold badges88 silver badges107 bronze badges
$endgroup$
1
You must log in to answer this question.
Not the answer you’re looking for? Browse other questions tagged
.
Not the answer you’re looking for? Browse other questions tagged
.
Аксиоматика:
– Число n > 1 является простым, если делится нацело только на единицу и на n;
– Число a делится нацело на b, если остаток от деления a на b равен нулю;
– От пеcтановки мест множителей произведение не меняется;
– Составным называется число, которое не является простым;
Следствие из первой и второй аксиом: для того, чтобы определить, является ли число n простым, необходимо для каждого 1 < i < n проверить остаток от деления n на i на рвенство нулю.
Следствие из первой, второй и третьей аксиом: если число n может быть представлено как произведение двух чисел a и b и a <= b, то для проверки n на простоту достаточно проверить на равенство нулю остаток от деления n на a.
Следствие из первой и четвёртой аксиом: если число n может быть разложено на множители, один или несколько из которых являются составными, то каждый из составных множителей также может быть разложен на множители и так до тех пор, пока среди всех множителей не окажутся лишь простые числа.
Из всего этого следует, что для проверки числа n на простоту достаточно проверить остаток от деления n на все простые числа i < n, для которых i <= n / i. Последнее условие получено из цепочки
n = a * b
b = n / a
a <= b
a <= n / a или !(n / a < a)
Данный подход позволит существенно понизить сложность алгоритма проверки на простоту (то есть, уменьшить количество итераций) за счёт хранения в памяти простых чисел, уже прошедших проверку.
Реализуем этот принцип.
using System;
using System.Collections.Generic;
/// <summary>
/// Функция проверки на простоту
/// </summary>
static bool IsPrime(int n, IEnumerable<int> primes)
{
if (n < 2)
return false;
foreach (int prime in primes)
{
if (n / prime < prime)
return true;
if (n % prime == 0)
return false;
}
return true;
}
Полагаем, что в объекте перечислимого типа primes хранятся все простые числа i, упорядоченные по возрастанию, где 2 <= i < n.
Далее, опишем функцию нахождения простого числа с индексом index, полагая, что индексация ведётся с нуля (то есть, для index = 0 функция вернёт 2). Для хранения найденных простых чисел будем использовать Queue< T > из System.Collections.Generic в качестве списка с возможностью добавления элемента в конец.
static int GetPrime(int index)
{
Queue<int> primes = new Queue<int>();
int found_count = 0;
for (int i = 2; ; i++)
{
if (IsPrime(i, primes))
{
if (index == found_count)
return i;
else
{
primes.Enqueue(i);
found_count++;
}
}
}
}
Ну, и Main():
static void Main()
{
// Инедксация ведётся с нуля, так что
// от порядкового номера отнимаем единичку.
const int index = 10001 – 1;
int result = GetPrime(index);
Console.WriteLine(result);
Console.ReadKey();
}
Ответ – 104743.
Проект Эйлера. Задача 7. Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #Проект Эйлера | |
| #Задача 7 | |
| #Выписав первые шесть простых чисел, получим 2, 3, 5, 7, 11 и 13. Очевидно, | |
| #что 6-ое простое число – 13. | |
| #Какое число является 10001-ым простым числом? | |
| # Ответ: 104743 | |
| #Решение на основе решето Эратосфена | |
| simple=[3] | |
| number=3 | |
| count=3 | |
| while count<=10001: | |
| number+=2 | |
| simpleNuber=True | |
| for i in simple: | |
| if number<i**2: #числа кратные i, начинают высчитывать с i(квадрат) | |
| break | |
| else: | |
| if number%i==0: | |
| simpleNuber=False | |
| break | |
| if simpleNuber==True: | |
| simple.append(number) | |
| count+=1 | |
| print(simple[-1]) |
