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

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

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .	Влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .

@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

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

Решение