Главная » Реализация известных алгоритмов на языке программирования Python

Решето Эратосфена - алгоритм определения простых чисел

Опубликовано plustilino в Январь 10, 2010 - 14:05. Changed Январь 3, 2011 - 18:48

Описание алгоритма

Решето Эратосфена – это алгоритм нахождения простых чисел до заданного числа n. В процессе выполнения данного алгоритма постепенно отсеиваются составные числа, кратные простым, начиная с 2.

Исходный код на Python

n = int(input("вывод простых чисел до числа ... "))
a = [0] * n # создание массива с n количеством элементов
for i in range(n): # заполнение массива ...
    a[i] = i # значениями от 0 до n-1
 
# вторым элементом является единица, которую не считают простым числом
# забиваем ее нулем.
a[1] = 0
 
m = 2 # замена на 0 начинается с 3-го элемента (первые два уже нули)
while m < n: # перебор всех элементов до заданного числа
    if a[m] != 0: # если он не равен нулю, то
        j = m * 2 # увеличить в два раза (текущий элемент простое число)
        while j < n:
            a[j] = 0 # заменить на 0
            j = j + m # перейти в позицию на m больше
    m += 1
 
# вывод простых чисел на экран (может быть реализован как угодно)
b = []
for i in a:
    if a[i] != 0:
        b.append(a[i])
 
del a
print (b)

Блок-схема

Блок-схема к алгоритму `Решето Эратосфена`
#1Опубликовано Гость в Ноябрь 20, 2011 - 07:33.

a=range(int(input("вывод

a=range(int(input("вывод простых чисел до числа ... ")))
for i in a:
    if i>1:
        for j in range(i+i,len(a),i):
            a[j]=0
        print i,
#2Опубликовано Гость в Июнь 23, 2011 - 13:10.

еще вариант

def Primes(N):
    primes = [i for i in range(1, N+1)]
    primes[0] = 0
 
    for i in xrange(0, N):
        if primes[i] != 0:
            for j in xrange(i+primes[i], N, primes[i]):
                primes[j] = 0
 
    return [x for x in primes if x != 0]
 
print Primes(34)

ЗЫ: писать на питоне, особенно после Си, одно удовольствие =)
#3Опубликовано Гость в Апрель 17, 2011 - 23:11.

Избавляемся от сишных замашек :)

Предлагаю использовать прелести языка, заменив

a = [0] * n # создание массива с n количеством элементов
for i in range(n): # заполнение массива ...
    a[i] = i # значениями от 0 до n-1

на

a = [i for i in range(n)]
#4Опубликовано Гость в Июнь 24, 2011 - 11:47.

или

a = range(n)