Метод решето эратосфена питон

Реализации алгоритмов/Решето Эратосфена

Решето́ Эратосфе́на — алгоритм нахождения всех простых чисел, не превышающих некоторое натуральное число n.

• 1 Реализации
  • 1.1 C/C++
    • 1.1.1 Обычный вариант
    • 1.1.2 Просеивание простыми до корня
    • 1.3.1 Базисный вариант
    • 1.3.2 Вариация по Эйлеру
    • 1.3.3 Поэтапная фильтровка проверками на делимость (не Эратосфен; медленно)
    • 1.3.4 Поэтапное решето, с немедленным отсеиванием (медленно)
    • 1.3.5 С отложенным отсеиванием, от квадратов простых чисел (гораздо быстрее)
    • 1.3.6 С комбинированным бесконечным решетом, от Richard Bird
    • 1.3.7 Просеивание через массив, посегментно между квадратами простых чисел
    • 1.5.1 Вариант № 1
    • 1.5.2 Вариант № 2
    • 1.5.3 Вариант № 3 (списковое включение)
    • 1.5.4 Вариант №4
    • 1.5.5 Вариант №5

    Реализации [ править ]

    Множество примеров реализации приведено в проекте rosettacode.org [1] . В данном разделе приводится несколько примеров на популярных языках программирования:

    C/C++ [ править ]

    Обычный вариант [ править ]

    int n; vectorchar> prime (n+1, true); prime[0] = prime[1] = false; for (int i=2; in; ++i) if (prime[i]) if (i * 1ll * i  n) //1ll для перевода в long long for (int j=i*i; jn; j+=i) prime[j] = false; 

    Просеивание простыми до корня [ править ]

    int n; vectorbool> prime (n + 1, true); prime[0] = prime[1] = false; for (int i = 2; i * i  n; ++i) // valid for n < 46340^2 = 2147395600if (prime[i]) for (int j = i * i; j  n; j += i) prime[j] = false; 

    Java [ править ]

    import java.util.Arrays; public class Eratosfen  boolean[] primes; public Eratosfen(int n)  primes=new boolean[n+1]; > public void fillSieve()  Arrays.fill(primes, true); primes[0] = false; primes[1] = false; for (int i = 2; i  primes.length; ++i)  if (primes[i])  for (int j = 2; i * j  primes.length; ++j)  primes[i * j] = false; > > > > > 

    Haskell [ править ]

    Базисный вариант [ править ]

    primesTo n = eratos [2..n] where eratos [] = [] eratos (p:xs) = p : eratos (xs `minus` [p*p, p*p+p..n]) minus (x:xs) (y:ys) = case (compare x y) of LT -> x : minus xs (y:ys) EQ -> minus xs ys GT -> minus (x:xs) ys minus xs _ = xs 

    Вариация по Эйлеру [ править ]

    primesToEU n = eulers [2..n] where eulers [] = [] eulers (p:xs) = p : eulers (xs `minus` takeWhile ( n) (map (p*) (p:xs))) -- eratos (p:xs) = p : eratos (xs `minus` takeWhile ( 

    Поэтапная фильтровка проверками на делимость (не Эратосфен; медленно) [ править ]

    primesT = sieve [2..] -- знаменитый код Дейвида Тёрнера where sieve (p:xs) = p : sieve [x | x  xs, rem x p > 0] 

    Поэтапное решето, с немедленным отсеиванием (медленно) [ править ]

    primesE = sieve [2..] where sieve (p:xs) = p : sieve (minus xs [p, p+p..]) -- или: -- ps = (map head . scanl minus [2..] . map (\p -> [p, p+p..])) ps 

    С отложенным отсеиванием, от квадратов простых чисел (гораздо быстрее) [ править ]

    primesEQ = 2 : sieve [3..] 4 primesEQ where sieve (x:xs) q (p:t) | x  q = x : sieve xs q (p:t) | otherwise = sieve (minus xs [q, q+p..]) (head t^2) t 

    С комбинированным бесконечным решетом, от Richard Bird [ править ]

    primesB = 2 : minus [3..] (foldr (\p r-> (p*p) : union [p*p+p, p*p+2*p..] r) [] primesB) union (x:xs) (y:ys) = case (compare x y) of LT -> x : union xs (y:ys) EQ -> x : union xs ys GT -> y : union (x:xs) ys 

    Просеивание через массив, посегментно между квадратами простых чисел [ править ]

    import Data.Array.Unboxed ps = 2 : [n | (px, r:q:_)  zip (inits ps) (tails (2 : map (^2) ps)) , (n, True)  assocs ( accumArray (\_ _ -> False) True (r+1,q-1) [ (m,()) | p  px , let s = div (r+p) p * p , m  [s, s+p .. q-1] ] :: UArray Int Bool ) ] 

    Python 2.x [ править ]

    Функция возвращает список простых и список составных чисел вплоть до заданного n:

    def eratosthenes (n): primes = [] multiples = [] for i in xrange(2, n + 1): if i not in multiples: primes.append(i) multiples.extend(xrange(i * i, n + 1, i)) return (primes, multiples) 

    Python 3.x [ править ]

    Вариант № 1 [ править ]

    Функция возвращает список («решето«), в котором все составные числа заменены нулями:

    def eratosthenes(n): # n - число, до которого хотим найти простые числа sieve = list(range(n + 1)) sieve[1] = 0 # без этой строки итоговый список будет содержать единицу for i in sieve: if i > 1: for j in range(2*i, len(sieve), i): sieve[j] = 0 return sieve 

    Вариант № 2 [ править ]

    n = int(input()) # число, до которого хотим найти простые числа numbers = list(range(2, n + 1)) for number in numbers: if number != 0: for candidate in range(2 * number, n+1, number): numbers[candidate-2] = 0 print(*list(filter(lambda x: x != 0, numbers))) # выводим простые числа 

    Вариант № 3 (списковое включение) [ править ]

    Полностью построено на генераторах списков.

    n = int(input()) s = [x for x in range(2, n+1) if x not in [i for sub in [list(range(2 * j, n+1, j)) for j in range(2, n // 2)] for i in sub]] print(s) 

    Вариант №4 [ править ]

    a, n = True, int(input()) #n - число, до которого хотим дойти for x in range(1,n): for y in range(1,n): if x != y and y != 1: if not x % y: a = False break if a == True: print(x,end=' ') a = True 

    Вариант №5 [ править ]

    Решение с множеством set, которое было тут ранее неверное, но ниже представлено решение, как в первом варианте, только с заменой нулей на пустоту. def eratosthenes(n): # n - число, до которого хотим найти простые числа sieve = list(range(n + 1)) sieve[1] = 0 # без этой строки итоговый список будет содержать единицу for i in sieve: if i > 1: for j in range(i + i, len(sieve), i): sieve[j] = 0 sieve1 = [x for x in sieve if x != 0] return sieve1 print(eratosthenes(n)) #где n - любое число 

    См. также [ править ]

    Примечания [ править ]

    Источник

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

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

    Чтобы понять данный алгоритм, вспомним, что числа являются простыми, если делятся только на единицу и самих себя. Первое простое число — это 2, второе простое число — это 3. Теперь начнем рассуждать:

    1. Все четные числа, кроме двойки, — составные, т. е. не являются простыми, так как делятся не только на себя и единицу, а также еще на 2.
    2. Все числа кратные трем, кроме самой тройки, — составные, так как делятся не только на самих себя и единицу, а также еще на 3.
    3. Число 4 уже выбыло из игры, так как делится на 2.
    4. Число 5 простое, так как его не делит ни один простой делитель, стоящий до него.
    5. Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

    Последний пункт вытекает из того, что сложные числа всегда можно представить как произведение простых. Поэтому если одно сложное число делится на другое сложное, то первое должно делиться на делители второго. Например, 12 делится на 6, делителями которого являются 2 и 3. Число 12 делится и на 2, и на 3.

    Алгоритм Эратосфена как раз заключается в последовательной проверке делимости чисел на предстоящие простые числа. Сначала берется первое простое и из ряда натуральных чисел высеиваются все кратные ему. Затем берется следующее простое и отсеиваются все кратные ему и так далее.

    При реализации алгоритма Эратосфена на языке программирования есть некоторая сложность. Допустим, мы помещаем натуральные числа до заданного числа N в массив. Далее в процессе выполнения алгоритма будем заменять обнаруженные сложные числа нулями. После выполнения алгоритма те ячейки массива, которые не содержат нули, содержат простые числа, которые выводятся на экран.

    Однако индексация массива начинается с нуля, а простые числа начинаются с двойки. Эта проблема решаема, но добавляет сложности в код. Поскольку алгоритм Эратосфена не такой уж простой, легче пренебречь началом и взять массив от 0 до N . Здесь важнее индексы, чем значения элементов. Значениями могут быть логические True , обозначающее простое число, и False , обозначающее сложное число.

    В данном примере реализации алгоритма Эратосфена на языке программирования Python список заполняется числами от 0 до N включительно так, что индексы элементов совпадают с их значениями. Далее все непростые числа заменяются нулями:

    N = int(input()) # Создается список из значений от 0 до N включительно primes = [i for i in range(N + 1)] # Вторым элементом списка является единица, которую # не считают простым числом. Забиваем ее нулем primes[1] = 0 # Начинаем с 3-го элемента i = 2 while i  N: # Если значение текущей ячейки до этого не было обнулено, # значит в этой ячейке содержится простое число if primes[i] != 0: # Первое кратное ему будет в два раза больше j = i + i while j  N: # и это число составное, # поэтому заменяем его нулем primes[j] = 0 # переходим к следующему числу, # которое кратно i (оно на i больше) j = j + i i += 1 # Избавляемся от всех нулей в списке primes = [i for i in primes if i != 0] print(primes) 

    35 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

    Источник

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

    Данная программа должна вывести все простые числа в заданном диапазоне (от 0 до n ) при помощи алгоритма «Решето Эратосфена».

    Решение задачи

    1. Принимаем значение определяющее верхнюю границу диапазона и записываем его в переменную n .
    2. Инициализируем переменную sieve («решето») множеством чисел от 2 до n .
    3. Используем цикл while , который прекратит свою работу, когда множество sieve станет пустым.
    4. Примем во внимание тот факт, что минимальное число в этом множестве (на первой итерации это будет 2) всегда простое.
    5. Выводим это число на экран.
    6. Далее удаляем это число вместе со всеми числами, кратными ему (в заданном диапазоне).
    7. Продолжаем это делать, пока множество sieve не станет пустым.
    8. Конец

    Исходный код

    Ниже дан исходный код для вывода всех простых чисел из заданного диапазона при помощи алгоритма под названием «решето Эратосфена». Результаты работы программы также даны ниже.

    n = int(input("Введите верхнюю границу диапазона: ")) sieve = set(range(2, n+1)) while sieve: prime = min(sieve) print(prime, end = "\t") sieve -= set(range(prime, n+1, prime))

    Объяснение работы программы

    1. Пользователь вводит верхнюю границу диапазона, и она записывается в переменную n .
    2. Инициализируем переменную sieve множеством всех чисел в диапазоне от 2 до n . Тип «множество» задается функцией set , а все числа диапазона определяются при помощи функции range .
    3. Цикл while будет работать, пока множество sieve не станет пустым.
    4. Переменная prime инициализируется минимальным значением из множества sieve . Обращаем внимание, что это всегда будет простое число. И это простое число выводится на экран.
    5. Затем это число и все числа, кратные ему, удаляются из множества sieve .
    6. Пункты 4 и 5 повторяются до тех пор, пока множество sieve не станет пустым, то есть количество элементов в нем станет равно 0.

    Результаты работы программы

    Пример 1: Введите верхнюю границу диапазона: 10 2 3 5 7 Пример 2: Введите верхнюю границу диапазона: 15 2 3 5 7 11 13

    Источник

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

    

    Статьи

    Введение

    В ходе статьи используя алгоритм “Решето Эратосфена” найдём все простые числа до заданного числа N в Python.

    Решето Эратосфена – это алгоритм нахождения всех простых чисел в диапазоне от 0, до заданного числа N.

    Написание кода

    Для начала дадим пользователю возможность ввода числа верхней границы диапазона:

    Используя генератор заполним список значениями от одного, до заданного числа N:

    n = int(input('Введите N: ')) a = [i for i in range(n + 1)]

    Так как единица не является простым числом, заменим её на ноль:

    n = int(input('Введите N: ')) a = [i for i in range(n + 1)] a[1] = 0

    Создадим переменную i равную двум, чтобы начать сразу с третьего элемента:

    n = int(input('Введите N: ')) a = [i for i in range(n + 1)] a[1] = 0 i = 2

    n = int(input('Введите N: ')) a = [i for i in range(n + 1)] a[1] = 0 i = 2 while i 

    n = int(input('Введите N: ')) a = [i for i in range(n + 1)] a[1] = 0 i = 2 while i 

    Преобразуем список в множество, после чего удалим все нули и выведем его:

    n = int(input('Введите N: ')) a = [i for i in range(n + 1)] a[1] = 0 i = 2 while i

    Заключение

    В ходе статьи мы с Вами научились использовать алгоритм “Решето Эратосфена” для нахождения всех простых чисел в заданном диапазоне и написали код на Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂

    Источник

    Читайте также:  Java regex one space