Задача Эйлера № 7 Про простые числа

@_ViDaR_ · Регистрация: 15.09.2021

Студворк — интернет-сервис помощи студентам

Условия задачи таковы

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

Какое число является 10001-м простым числом?

Вот такое решение у меня получилось. Нужно добавить проверку, чтобы цикл прекратился, как дойдет до 10001 числа, это сделаю, пока проблема со скоростью выполнения. Как можно ускорить это все? Смотрел правильный ответ, должно получится число 104743, я беру входными данными 105000 и все встает просто)) Даже добавил индикатор прогресса, а то скучно так смотреть.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from tqdm import tqdm 
 
from time import sleep
i = int(input('>>> '))
 
 
 
 
good_list=[]
 
list_n = [l for l in range (2, i)]
 
for pg in tqdm(range(100)):
    while True:
        l = 1
        try:
            s = list_n[0]
            good_list.append(list_n[0])
            list_n.remove(s)
        except IndexError:
            break
 
        while l*s < i:
            p = l*s
            try:
                list_n.remove(p)
            except ValueError:
                l+=1
            
            
        
    sleep(.01)
 
 
print(good_list)
input()

@alilxxey · 15.09.2021, 18:46

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def isPrime(n):
    if n % 2 == 0:
        return n == 2
    d = 3
    while d * d <= n and n % d != 0:
        d += 2
    return d * d > n
 
 
i = int(input())
k = 1
ct = 0
while ct <= i:
    if isPrime(k):
        ct += 1
    k += 1
print(k - 1)

enx · 15.09.2021, 18:48

Делал как то давно, два варианта:

1.

Python
1
2
3
from sympy import prime
 
print(prime(int(input())))

2.

Python
1
2
3
4
5
6
7
8
from sympy import isprime
 
a, b, c = int(input()), 0, 0
while a != b:
    c += 1
    if isprime(c):
        b += 1
print(c)

@Gdez · 15.09.2021, 19:04

_ViDaR_, есть приближенная формула для n > 14 -> n-ое простое число < вычисленного значения

Python
1
2
3
from math import log
n = 15
print(int((log(n) + log(log(n)) - 0.5)*n))

@Catstail · 18.09.2021, 21:12

enx, прекрасные решения. Только автор у них - разработчик sympy

enx · 18.09.2021, 21:22

Я вам уже говорил, напишу вам 10 вариаций решета Эратосфена...запакую в def, выпущу свой модуль на py....который не пройдет модерацию, потому что уже есть 20 реализаций на СPy, которые быстрее в 10 раз core python...вот скажите честно, вы хоть раз смотрели, как работает возведение в степень библиотеки math.py?

А я смотрел...вопрос, вы можете лучше?
Если да, кидайте код на С.

Лично я - не могу.

@Catstail · 19.09.2021, 08:38

Сообщение от enx

А я смотрел...вопрос, вы можете лучше?

- эффективнее? Нет. Я не знаю, в чем истинная цель проекта Эйлер, но для меня это возможность изучать алгоритмы, а не библ. вызовы. Решение, которое делает за вас библиотека, для меня неинтересно. Это как сказать: "отсортируй массив" и получить ответ "sorted(x)". Решение эффективное, но для меня неинтересное. Впрочем, я бы поставил за него 5+ дедушке Гвидо. Он, несомненно, молодец!

Сообщение от enx

вы хоть раз смотрели, как работает возведение в степень библиотеки math.py?

- нет, но догадываюсь... Я не люблю эту функцию (и не только в Питоне) и стараюсь заменять ее. Для этого есть разные способы:

- для целых показателей - прямое умножение
- для дробных и прочих - экспонента и логарифм (их я, естественно, беру стандартными)
- преобразование выражения таким образом, чтобы избежать возведения в степень

Новые блоги и статьи Все статьи Все блоги /
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .
Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .

@Catstail Супер-модератор 38203 / 21135 / 4310 Регистрация: 12.02.2012 Сообщений: 34,741 Записей в блоге: 14
	18.09.2021, 21:12
	enx, прекрасные решения. Только автор у них - разработчик sympy 1

enx 1190 / 766 / 277 Регистрация: 05.09.2021 Сообщений: 1,772
	18.09.2021, 21:22
	Я вам уже говорил, напишу вам 10 вариаций решета Эратосфена...запакую в def, выпущу свой модуль на py....который не пройдет модерацию, потому что уже есть 20 реализаций на СPy, которые быстрее в 10 раз core python...вот скажите честно, вы хоть раз смотрели, как работает возведение в степень библиотеки math.py? А я смотрел...вопрос, вы можете лучше? Если да, кидайте код на С. Лично я - не могу. 0

Опции темы