Как найти количество простых чисел в питоне

I needed the same thing and decided to create my own to excercise on many things.

Here: primes.py

WARNING: I tried to bugfix it as much as I could and making checks on everything, but I am still an amateur, so I do NOT guarantee advanced or professional checks and absence of bugs. Use at your own risk.

It will dynamically sieve primes numbers as needed, store them in a compressed binary format and retrieve them from there.

The most useful class is ‘primes’. The class itself can be used as a generator, a container, subscripted and sliced.

WARNING: be careful iterating on infinite sequences!

from primes import primes

for p in primes:  # 2, 3, 5, 7, 11, ...
    pass
primes[0]  # 2
primes[4]  # 11
primes[1:6:2] # primes object, generates 3, 7, 13
7 in primes  # True
8 in primes  # False

‘primes also has useful methods:

primes.estimate(1000)  # 7830, real 1000th prime is 7927
primes.check(7)  # True
primes.index_of(11)  # 4 <- primes[4] = 11
primes.count_upto(10) # 4 <- len([2,3,5,7])
primes.sieve(5, 10)  # [5, 7] 
primes.in_range(5, 20, 2)  # primes object, generates 5, 11, 13, 19
primes.factor(12)  # {2:2, 3:1} <- 12 = 2^2 * 3^1
primes.phi(6)  # 6 <- Euler phi function,  number of smaller co-primes

And the primes objects are themselves generator, containers, subscriptable and sliceable, but on sublists of primes:

primerange1 = primes(1, None, 2)  # generator
for p in primerange1:  # 3, 7, 13, 19, ...
    pass
primerange1[1]  # 7
primerange1[:4:-1]  # generator: 13, 7, 3
2 in primerange1  # False

primerange2 = primes(6, 0, -2)  # generates 13, 7, 3
len(primerange2)  # 3
reversed(primerange2)  # primes object, generates 3, 7, 13

The class ‘plib’ is used to manage the library and its settings.

I hope someone will find it useful, and I’ll be glad to receive any suggestion or bug report.

Алгоритм нахождения простых чисел

Оптимизация алгоритма нахождения простых чисел

2 3 5 7 11 13 17 19 23 29 31… $250.000…

Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.

Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.

Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.

# Листинг 1
# вводим N
n = input("n=")
# создаем пустой список для хранения простых чисел
lst = []
# в k будем хранить количество делителей
k = 0
# пробегаем все числа от 2 до N
for i in xrange(2, n+1):
    # пробегаем все числа от 2 до текущего
    for j in xrange(2, i):
        # ищем количество делителей
        if i % j == 0:
            k = k + 1
    # если делителей нет, добавляем число в список
    if k == 0:
        lst.append(i)
    else:
        k = 0
# выводим на экран список
print lst

Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.

# Листинг 2
n = input("n=")
lst = []
for i in xrange(2, n+1):
    for j in xrange(2, i):
        if i % j == 0:
            # если делитель найден, число не простое.
            break
    else:
        lst.append(i)
print lst

Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.

# Листинг 3
n = input("n=")
lst=[]
for i in xrange(2, n+1):
    # пробегаем по списку (lst) простых чисел
    for j in lst:
        if i % j == 0:
            break
    else:
        lst.append(i)
print lst

А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.

# Листинг 4 
from math import sqrt
n = input("n=")
lst=[]
for i in xrange(2, n+1):
    for j in lst:
        if j > int((sqrt(i)) + 1):
            lst.append(i)
            break
        if (i % j == 0):
            break
    else:
        lst.append(i)
print lst

Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.

# Листинг 5
from math import sqrt
n = input("n=")
lst=[]
for i in xrange(2, n+1):
    if (i > 10):
        if (i%2==0) or (i%10==5):
            continue
    for j in lst:
        if j > int((sqrt(i)) + 1):
            lst.append(i)
            break
        if (i % j == 0):
            break
    else:
        lst.append(i)
print lst

В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:

# Листинг 6
from math import sqrt
n = input("n=")
lst=[2]
for i in xrange(3, n+1, 2):
    if (i > 10) and (i%10==5):
        continue
    for j in lst:
        if j > int((sqrt(i)) + 1):
            lst.append(i)
            break
        if (i % j == 0):
            break
    else:
        lst.append(i)
print lst

Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.

P.S.
Благодаря замечаниям получаем Листинг 7:

# Листинг 7
n = input("n=")
lst=[2]
for i in xrange(3, n+1, 2):
	if (i > 10) and (i%10==5):
		continue
	for j in lst:
		if j*j-1 > i:
			lst.append(i)
			break
		if (i % j == 0):
			break
	else:
		lst.append(i)
print lst

при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

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

# Листинг 8
n = input("n=")
a = range(n+1)
a[1] = 0
lst = []

i = 2
while i <= n:
    if a[i] != 0:
        lst.append(a[i])
        for j in xrange(i, n+1, i):
            a[j] = 0
    i += 1
print lst

Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143

Простое число — это натуральное число, которое больше 1 и не имеет положительного делителя, кроме 1 и самого себя, например 2, 3, 5, 7, 11, 13 и так далее.

Пользователю даются два целых числа, нижнее значение и верхнее значение. Задача состоит в том, чтобы написать программу Python для вывода всех простых чисел в заданном интервале (или диапазоне).

Чтобы напечатать все простые числа в заданном интервале, пользователь должен выполнить следующие шаги:

• Шаг 1: Переберите все элементы в заданном диапазоне.
• Шаг 2: Проверьте для каждого числа, есть ли у него какой-либо множитель между 1 и самим собой.
• Шаг 3: Если да, то число не простое, и оно перейдет к следующему числу.
• Шаг 4: Если нет, то это простое число, и программа распечатает его и проверит следующее число.
• Шаг 5: Цикл прервется, когда будет достигнуто верхнее значение.

Пример: код Python для печати простого числа в заданном интервале.

 
# First, we will take the input: 
lower_value = int(input("Please, Enter the Lowest Range Value: ")) 
upper_value = int(input("Please, Enter the Upper Range Value: ")) 
 
print("The Prime Numbers in the range are: ") 
for number in range(lower_value, upper_value + 1): 
    if number > 1: 
        for i in range(2, number): 
            if(number % i) == 0: 
                break 
        else: 
            print(number) 

Выход:

Please, Enter the Lowest Range Value:  14 
Please, Enter the Upper Range Value:  97 
The Prime Numbers in the range are:  
17 
19 
23 
29 
31 
37 
41 
43 
47 
53 
59 
61 
67 
71 
73 
79 
83 
89 
97 

Заключение

В этом уроке мы показали, как написать код для печати простых чисел в заданном диапазоне чисел.

# Написать два алгоритма нахождения i-го по счёту простого числа. # Функция нахождения простого числа должна принимать на вход натуральное и возвращать соответствующее простое число. # Проанализировать скорость и сложность алгоритмов. # # Первый — с помощью алгоритма «Решето Эратосфена». # Второй — без использования «Решета Эратосфена». # Тестовая функция проверяет до 1229-го простого числа. import cProfile def test(num, n=10000): sieve = [i for i in range(n)] sieve[1] = 0 for i in range(2, n): if sieve[i] != 0: j = i + i while j < n: sieve[j] = 0 j += i res = [i for i in sieve if i != 0] print(f’Количество простых чисел в диапазоне до {n}: {len(res)}‘) assert num < len(res) return res[num – 1] def eratosthenes_sieve(n): count = 1 start = 3 end = 4 * n sieve = [i for i in range(start, end) if i % 2 != 0] prime = [2] if n == 1: return 2 while count < n: for i in range(len(sieve)): if sieve[i] != 0: count += 1 if count == n: return sieve[i] j = i + sieve[i] while j < len(sieve): sieve[j] = 0 j += sieve[i] prime.extend([i for i in sieve if i != 0]) start, end = end, end + 2 * n sieve = [i for i in range(start, end) if i % 2 != 0] for i in range(len(sieve)): for num in prime: if sieve[i] % num == 0: sieve[i] = 0 break # py -m timeit -n 100 -s “import Lesson_4_Task_2” “Lesson_4_Task_2.eratosthenes_sieve(10)” # “Lesson_4_Task_2.eratosthenes_sieve(10)” # 100 loops, best of 5: 4.69 usec per loop # “Lesson_4_Task_2.eratosthenes_sieve(100)” # 100 loops, best of 5: 201 usec per loop # “Lesson_4_Task_2.eratosthenes_sieve(1000)” # 100 loops, best of 5: 17.3 msec per loop # Предположительно, алгоритм сложности O(n**2). Увеличение количества чисел в 10 раз # увеличивает время выполнения приблизительно в 100 раз # cProfile.run(‘eratosthenes_sieve(10)’) # 1 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:31(eratosthenes_sieve) # 1 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:36(<listcomp>) # cProfile.run(‘eratosthenes_sieve(100)’) # 1 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:31(eratosthenes_sieve) # 1 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:36(<listcomp>) # 1 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:58(<listcomp>) # 1 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:61(<listcomp>) # cProfile.run(‘eratosthenes_sieve(1000)’) # 1 0.022 0.022 0.023 0.023 Lesson_4_Task_2.py:31(eratosthenes_sieve) # 1 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:36(<listcomp>) # 2 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:58(<listcomp>) # 2 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:61(<listcomp>) # Время выполнения нарастает. Рекурсий нет. def search_prime(n): count = 1 number = 1 prime = [2] if n == 1: return 2 while count != n: number += 2 for num in prime: if number % num == 0: break else: count += 1 prime.append(number) return number # py -m timeit -n 100 -s “import Lesson_4_Task_2” “Lesson_4_Task_2.search_prime(10)” # “Lesson_4_Task_2.search_prime(10)” # 100 loops, best of 5: 3.35 usec per loop # “Lesson_4_Task_2.search_prime(100)” # 100 loops, best of 5: 187 usec per loop # “Lesson_4_Task_2.search_prime(1000)” # 100 loops, best of 5: 18 msec per loop # Сложность близка к O(n**2) # Скорость работы обоих алгоритмов на данных объемах данных практически одинакова. # cProfile.run(‘search_prime(1000)’) # 1 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:97(search_prime) 10 # 1 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:97(search_prime) 100 # 1 0.019 0.019 0.019 0.019 Lesson_4_Task_2.py:97(search_prime) 1000 # Время выполнения нарастает. Рекурсий нет. # ВЫВОД: # Сложность алгоритмов и время их работы приблизительно одинаковые. n = 521 # if eratosthenes_sieve(n) == test(n): # print(f'{n}-ое простое число {eratosthenes_sieve(n)}’) # print(‘OK’) # else: # print(‘Ошибка’) # if search_prime(n) == test(n): # print(f'{n}-ое простое число {search_prime(n)}’) # print(‘OK’) # else: # print(‘Ошибка’)