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

@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() выводит фигурные скобки {}, просто нужно избавиться от нулей через список, а он выводится в квадратных скобках [].
Спасибо за алгоритм. ))

Новые блоги и статьи Все статьи Все блоги /
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .

@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

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

Решение