Алгоритм нахождения простых чисел
Время на прочтение
3 мин
Количество просмотров 432K
Оптимизация алгоритма нахождения простых чисел
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
Описание задачи
Программа принимает на вход число и проверяет, простое оно или нет.
Решение задачи
- Принимаем на вход число и записываем его в отдельную переменную.
- Инициализируем переменную, которая будет выполнять роль счетчика, значением
0
. - Организуем цикл
for
в диапазоне от2
до значения проверяемого числа, деленного на2
(речь идет, конечно, о целочисленном делении). - Затем находим количество делителей нашего числа. При помощи условного оператора
if
мы проверяем, делится ли число без остатка, и затем, если делится, увеличиваем наш счетчик на единицу. - Если число делителей равно
0
, то проверяемое число является простым. - Выводим результат на экран.
- Конец.
Исходный код
Ниже дан исходный код, который осуществляет проверку числа на простоту. Результаты работы программы также даны ниже.
a = int(input("Введите число: ")) k = 0 for i in range(2, a // 2+1): if (a % i == 0): k = k+1 if (k <= 0): print("Число простое") else: print("Число не является простым")
Объяснение работы программы
- Пользователь вводит число, и оно сохраняется в переменную
a
. - Инициализируем переменную
k
значением0
. Эта переменная будет выполнять роль счетчика. - Запускаем цикл
for
в диапазоне от2
до значения проверяемого числа, деленного на2
(речь идет, конечно, о целочисленном делении). Напоминаем, что само число и1
делителями мы считать не будем. - Затем, при помощи инструкции
if
, на каждой итерации цикла мы проверяем, делится ли наше число без остатка на числа из выбранного диапазона цикла. Если делится, то переменнаяk
, выполняющая роль счетчика, увеличивается на единицу. - Если число делителей равно
0
, то проверяемое число является простым. - Выводим полученный результат на экран.
Результаты работы программы
Пример 1: Введите число: 7 Число простое Пример 2: Введите число: 35 Число не является простым
Еще более 50 задач на числа в нашем телеграм канале Python Turbo. Уютное сообщество Python разработчиков.
Given a positive integer N, The task is to write a Python program to check if the number is Prime or not in Python.
Examples:
Input: n = 11 Output: True Input: n = 1 Output: False Explanation: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few prime numbers are {2, 3, 5, 7, 11, ….}.
Prime Number Program in Python
The idea to solve this problem is to iterate through all the numbers starting from 2 to (N/2) using a for loop and for every number check if it divides N. If we find any number that divides, we return false. If we did not find any number between 2 and N/2 which divides N then it means that N is prime and we will return True.
Python3
num
=
11
if
num >
1
:
for
i
in
range
(
2
,
int
(num
/
2
)
+
1
):
if
(num
%
i)
=
=
0
:
print
(num,
"is not a prime number"
)
break
else
:
print
(num,
"is a prime number"
)
else
:
print
(num,
"is not a prime number"
)
Output
11 is a prime number
Time complexity: O(n)
Auxiliary space: O(1)
Fastest Algorithm to Find Prime Numbers
Instead of checking till n, we can check till √n because a larger factor of n must be a multiple of a smaller factor that has been already checked. Now let’s see the code for the first optimization method ( i.e. checking till √n )
Python3
from
math
import
sqrt
n
=
1
prime_flag
=
0
if
(n >
1
):
for
i
in
range
(
2
,
int
(sqrt(n))
+
1
):
if
(n
%
i
=
=
0
):
prime_flag
=
1
break
if
(prime_flag
=
=
0
):
print
(
"True"
)
else
:
print
(
"False"
)
else
:
print
(
"False"
)
Time complexity: O(sqrt(n))
Auxiliary space: O(1)
Check Prime Numbers Using recursion
We can also find the number prime or not using recursion. We can use the exact logic shown in method 2 but in a recursive way.
Python3
from
math
import
sqrt
def
Prime(number,itr):
if
itr
=
=
1
:
return
True
if
number
%
itr
=
=
0
:
return
False
if
Prime(number,itr
-
1
)
=
=
False
:
return
False
return
True
num
=
13
itr
=
int
(sqrt(num)
+
1
)
print
(Prime(num,itr))
Time complexity: O(sqrt(n))
Auxiliary space: O(sqrt(n))
Check the Prime Trial Division Method
Python3
def
is_prime_trial_division(n):
if
n <
=
1
:
return
False
for
i
in
range
(
2
,
int
(n
*
*
0.5
)
+
1
):
if
n
%
i
=
=
0
:
return
False
return
True
print
(is_prime_trial_division(
11
))
Time complexity: O(sqrt(n))
Auxiliary space: O(sqrt(n))
RECOMMENDED ARTICLE – Analysis of Different Methods to find Prime Number in Python
Using a while loop to check divisibility:
Approach:
Initialize a variable i to 2.
While i squared is less than or equal to n, check if n is divisible by i.
If n is divisible by i, return False.
Otherwise, increment i by 1.
If the loop finishes without finding a divisor, return True.
Python3
import
math
def
is_prime(n):
if
n <
2
:
return
False
i
=
2
while
i
*
i <
=
n:
if
n
%
i
=
=
0
:
return
False
i
+
=
1
return
True
print
(is_prime(
11
))
print
(is_prime(
1
))
Time Complexity: O(sqrt(n))
Auxiliary Space: O(1)
METHOD:USING MATH
APPROACH:
The code implements a basic approach to check if a number is prime or not, by traversing all the numbers from 2 to sqrt(n)+1 and checking if n is divisible by any of those numbers.
ALGORITHM:
1.Check if the given number n is less than or equal to 1, if yes, return False.
2.Traverse all numbers in the range of 2 to sqrt(n)+1.
3.Check if n is divisible by any of the numbers from 2 to sqrt(n)+1, if yes, return False.
4.If n is not divisible by any of the numbers from 2 to sqrt(n)+1, return True.
Python3
import
math
def
is_prime(n):
if
n <
=
1
:
return
False
for
i
in
range
(
2
,
int
(math.sqrt(n))
+
1
):
if
n
%
i
=
=
0
:
return
False
return
True
n
=
11
print
(is_prime(n))
Time complexity: O(sqrt(n))
The time complexity of the code is O(sqrt(n)) because we traverse all numbers in the range of 2 to sqrt(n)+1 to check if n is divisible by any of them.
Auxiliary Space: O(1)
The space complexity of the code is O(1) because we are only using a constant amount of memory to store the input number n and the loop variables.
Method: Using sympy.isprime() method
In the sympy module, we can test whether a given number n is prime or not using sympy.isprime() function. For n < 264 the answer is definitive; larger n values have a small probability of actually being pseudoprimes.
N.B.: Negative numbers (e.g. -13) are not considered prime number.
Syntax:
sympy.isprime()
Python3
from
sympy
import
*
geek1
=
isprime(
30
)
geek2
=
isprime(
13
)
geek3
=
isprime(
2
)
print
(geek1)
print
(geek2)
print
(geek3)
Output
False True True
Time Complexity: O(sqrt(n)), where n is the input number.
Auxiliary Space: O(1)
Last Updated :
09 May, 2023
Like Article
Save Article
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [2422000; 2422080], простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа выведите его номер по порядку.
мой способ дает бесконечное выполнение программы
for x in range(2422000, 2422080):
a = []
for n in range(1,x):
if x%n==0 and (x==n or n==1):
a.append(n)
print(a)
Эникейщик
25.1k7 золотых знаков30 серебряных знаков46 бронзовых знаков
задан 19 дек 2020 в 21:39
4
По идее как то так
a = []
for x in range(2422000, 2422080):
d = 2
while x % d != 0:
d += 1
if d == x:
a.append(x)
print(a)
ответ дан 19 дек 2020 в 22:18
KersKers
3,1562 золотых знака7 серебряных знаков16 бронзовых знаков
Попробуйте так:
import math
def is_prime(i):
m = min(i, int(math.sqrt(b)))
l = range(2, m)
r = map(lambda x: i % x == 0, l)
return not any(r)
a = 2422000
b = 2422080
ls = range(a, b)
_list = list(filter(is_prime, ls))
print(*[ f'{i+1}: {v}' for i, v in enumerate(_list)], sep='n')
ответ дан 19 дек 2020 в 22:18
S. NickS. Nick
70.2k96 золотых знаков36 серебряных знаков55 бронзовых знаков
1
Под словами «номер по порядку» имеется в виду номер в списке (2422000, 2422080), или номер числа в списке простых чисел? Если первый вариант, то решение такое:
for i in range(2422000, 2422081):
for j in range(2, i // 2):
if i % j == 0: break
else: print(i - 2421999, i)
ответ дан 19 дек 2020 в 21:45
Попробуйте через списковую сборку, в первом списке поставьте нужный интервал в range(2, 1001)…, числа до 1000 поставил для примера,
вот:
print([x for x in range(2, 1001) if not [n for n in range(2, x) if not x % n]])
или
print([x for x in range(2, 1001) if all(x % t for t in range(2, int(math.sqrt(x))+1))])
ответ дан 13 июн 2021 в 19:39
PoMaXaPoMaXa
12 бронзовых знака
1
for i in range(2422000, 2422081):
deli=[]
for a in range(2,i+1):
if i%a==0:
deli.append(a)
if len(deli)>1:
break
if len(deli)==1:
print(deli)
ответ дан 23 июн 2021 в 10:14
1
Простое число — это натуральное число, которое больше 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
Заключение
В этом уроке мы показали, как написать код для печати простых чисел в заданном диапазоне чисел.
Изучаю Python вместе с вами, читаю, собираю и записываю информацию опытных программистов.