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

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

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@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

Опции темы

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

Решение