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

@aassii · Регистрация: 12.10.2018

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

Как реализовать алгоритм "Решето Эратосфена" для поиска простых чисел не больших N ?

Кликните здесь для просмотра всего текста

Ввод:
23
Вывод:
[2, 3, 5, 7, 11, 13, 17, 19, 23]

Код:

Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
n=int(input())
l=[i for i in range(2,n+1)]
l1=[]
while len(l)>0:
    l1.append(l[0])
    i=1
    while i<len(l):
        if l[i]%l[0]==0:
            del l[i]
        else:
            i+=1
    del l[0]
print(l1)

Тайм-лимит на некоторых тестах!

@Dax · 04.04.2019, 22:38

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def isprime(n):
    mliist=[]
    for  i in range(n+1):
        mliist.append(i)
    mliist[1]=0
    i=2
    while i<=n:
        if mliist[i]!=0:
            j=i+i
            while j<=n:
                mliist[j]=0
                j=j+i
        i+=1
    mliist=set(mliist)
    mliist.remove(0)
    print(mliist)
 
 
if __name__ == '__main__':
    n=int(input())
    isprime(n)

@aassii · 04.04.2019, 22:57 **[ТС]**

Dax, во всех тестах пишет "Wrong answer" ?!

@Dax · 04.04.2019, 23:00

aassii, а так?

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def  isprime(d):
    import math
 
    def is_prime(i):
        m = min(i, int(math.sqrt(n)))
        l = range(2, m)
        r = map(lambda x: i % x == 0, l)
        return not any(r)
 
    n = 100
    ls = range(2, n)
    ls2 = list(filter(is_prime, ls))
    print(ls2)
    # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
if __name__ == '__main__':
    d=int(input())
    isprime(d)

@aassii · 04.04.2019, 23:01 **[ТС]**

Dax, Ваша первая программа выводит фигурные скобки {}, а нужно квадратные скобки [] (как в списках).

@Dax · 04.04.2019, 23:05

Вывод моей программы прилагаю ниже, точнее обеих программ

@aassii · 04.04.2019, 23:34 **[ТС]**

Dax, Ваша вторая программа независимо от входных данных всегда выводит один и тот же результат:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Добавлено через 49 секунд
Я работаю в IDLE 3.7.0.

Добавлено через 20 минут
Dax, Вот https://www.python.org/downloads/, проверьте пожалуста работу ваших программ.

Добавлено через 4 минуты
Dax, У вас на втором скрине выводится результат в фигурных {} дужках?

@Dax · 04.04.2019, 23:53

aassii, все зависит оот того, на какой версии python писать, я писал гна 3.6, а в Вашей тестирующнй системе не знаю какой, возможно, от тогго ии идет разница по ответам

Добавлено через 1 минуту
Вы просили реализовать алгоритм, это сделано.

@aassii · 05.04.2019, 00:06 **[ТС]**

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

все зависит оот того, на какой версии python писать, я писал гна 3.6, а в Вашей тестирующнй системе не знаю какой, возможно, от тогго ии идет разница по ответам

В тестирующей системе стоит Python3 3.4.3
Разница по ответам идет потому, что ваша первая программа выводит фигурные скобки {}, а нужно выводить квадратные [] скобки. ))

Добавлено через 9 минут

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

Вы просили реализовать алгоритм, это сделано.

Извините пожалуста, но нет.
Dax, вы писали в PyCharm, и ваша первая программа выводит фигурные скобки {}, а нужно квадратные скобки [] (как в списках).
Dax, Ваша вторая программа независимо от входных данных всегда выводит один и тот же результат:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Вот https://www.python.org/downloads/, проверьте пожалуста работу ваших программ.
Я работаю в IDLE 3.7.0.
Dax, все равно огромное спасибо за попытку помощи))

@Dax · 05.04.2019, 08:59

aassii, разница,так же,если верно помню,в написани ф-ции print,плтому,тестирующий интерпритатор и видит скобки.
Ничем тут помочь не могу,я не устроитель данной олимпиады. Индекс idle обычно с индеесом версии python cовпадает,оттуда тоже может идти ошибка:для 3.4 писать на 3.7,оно,конечно,проблема будет.

@aassii · 06.04.2019, 19:59 **[ТС]**

Dax, проблема оказывается в том, что не нужно массив преобразовывать во множество, чтобы избавится от нулей, set() выводит фигурные скобки {}, просто нужно избавиться от нулей через список, а он выводится в квадратных скобках [].
Спасибо за алгоритм. ))

Новые блоги и статьи Все статьи Все блоги /
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .

@aassii 26 / 25 / 14 Регистрация: 12.10.2018 Сообщений: 240
	04.04.2019, 22:57 [ТС]
	Dax, во всех тестах пишет "Wrong answer" ?! 0

@aassii 26 / 25 / 14 Регистрация: 12.10.2018 Сообщений: 240
	04.04.2019, 23:01 [ТС]
	Dax, Ваша первая программа выводит фигурные скобки {}, а нужно квадратные скобки [] (как в списках). 0

@Dax 1356 / 653 / 207 Регистрация: 23.03.2014 Сообщений: 3,057
	04.04.2019, 23:05
	Вывод моей программы прилагаю ниже, точнее обеих программ Миниатюры 0

@aassii 26 / 25 / 14 Регистрация: 12.10.2018 Сообщений: 240
	04.04.2019, 23:34 [ТС]
	Dax, Ваша вторая программа независимо от входных данных всегда выводит один и тот же результат: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] Добавлено через 49 секунд Я работаю в IDLE 3.7.0. Добавлено через 20 минут Dax, Вот https://www.python.org/downloads/, проверьте пожалуста работу ваших программ. Добавлено через 4 минуты Dax, У вас на втором скрине выводится результат в фигурных {} дужках? 0

@Dax 1356 / 653 / 207 Регистрация: 23.03.2014 Сообщений: 3,057
	04.04.2019, 23:53
	aassii, все зависит оот того, на какой версии python писать, я писал гна 3.6, а в Вашей тестирующнй системе не знаю какой, возможно, от тогго ии идет разница по ответам Добавлено через 1 минуту Вы просили реализовать алгоритм, это сделано. 0

@Dax 1356 / 653 / 207 Регистрация: 23.03.2014 Сообщений: 3,057
	05.04.2019, 08:59
	aassii, разница,так же,если верно помню,в написани ф-ции print,плтому,тестирующий интерпритатор и видит скобки. Ничем тут помочь не могу,я не устроитель данной олимпиады. Индекс idle обычно с индеесом версии python cовпадает,оттуда тоже может идти ошибка:для 3.4 писать на 3.7,оно,конечно,проблема будет. 0

@aassii 26 / 25 / 14 Регистрация: 12.10.2018 Сообщений: 240
	06.04.2019, 19:59 [ТС]
	Dax, проблема оказывается в том, что не нужно массив преобразовывать во множество, чтобы избавится от нулей, set() выводит фигурные скобки {}, просто нужно избавиться от нулей через список, а он выводится в квадратных скобках []. Спасибо за алгоритм. )) 0

Опции темы

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

Решение