Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [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
Given two positive integers start and end. The task is to write a Python program to print all Prime numbers in an Interval.
Definition: 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, ….}.
Python Program for Prime Number
The idea to solve this problem is to iterate the val from start to end using a Python loop and for every number, if it is greater than 1, check if it divides n. If we find any other number which divides, print that value.
Python3
def prime(x, y):
prime_list = []
for i in range(x, y):
if i == 0 or i == 1:
continue
else:
for j in range(2, int(i/2)+1):
if i % j == 0:
break
else:
prime_list.append(i)
return prime_list
starting_range = 2
ending_range = 7
lst = prime(starting_range, ending_range)
if len(lst) == 0:
print("There are no prime numbers in this range")
else:
print("The prime numbers in this range are: ", lst)
Output
The prime numbers in this range are: [2, 3, 5]
Time Complexity: O(N2), where N is the size of the range.
Auxiliary Space: O(N), since N extra space has been taken.
Optimized way to find a Prime Number
The idea to solve this problem is to iterate the value from start to end using a for loop and for every number if it is divisible by any number except 1 and itself (prime number definition) then the flag variable will become 1. And in the next block if the flag value is zero then the only element will be appended to the list.
Step and implementation:
Step 1: Declare the flag and list.
Step 2: We will check the elements if it is divisible or not. (prime number definition)
Step 3: If divisible then flag =1 and break. if not divisible then flag =0.
Step 4: If flag=0, then the element is appended to the list.
Step 5: Return the list.
Python3
def prime(starting_range, ending_range):
lst=[]
flag=0
for i in range(starting_range, ending_range):
for j in range(2,i):
if(i%j==0):
flag=1
break
else:
flag=0
if(flag==0):
lst.append(i)
return lst
starting_range = 2
ending_range = 7
lst = prime(starting_range, ending_range)
if len(lst) == 0:
print("There are no prime numbers in this range")
else:
print("The prime numbers in this range are: ", lst)
Output
The prime numbers in this range are: [2, 3, 5]
Time Complexity: O(N2), where N is the size of the range.
Auxiliary Space: O(N): since N extra space has been taken
Sieve of Eratosthenes Method:
The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than N when N is smaller than 10 million or so.
Steps and implementation:
- Create a boolean array prime[srt to n] and initialize all its entries as true.
- Mark prime[0] and prime[1] as false because they are not prime numbers.
- Starting from p = srt, for each prime number p less than or equal to the square root of n, mark all multiples of p greater than or equal to p*p as composite by setting prime[i] to false.
- Finally, print all prime numbers between srt and n.
Below is the implementation:
Python3
import math
def SieveOfEratosthenes(srt, n):
prime = [True for i in range(n + 2 - srt)]
prime[0] = False
prime[1] = False
for p in range(srt, int(math.sqrt(n))+1):
if prime[p] == True:
for i in range(p*p, n+1, p):
prime[i] = False
for p in range(srt, n+1):
if prime[p]:
print(p, end=" ")
if __name__ == "__main__":
srt = 1
end = 10
SieveOfEratosthenes(srt, end)
Complexity Analysis:
Time Complexity:
The time complexity of the Sieve of Eratosthenes algorithm is O(n*log(log(n))) as it iterates over all numbers from 2 to n and removes all the multiples of each prime number.
In this code, the algorithm is applied only to a range [srt, n], which reduces the time complexity to O((n-srt+1)*log(log(n))) for the range [srt, n]. The loop for marking the multiples of each prime number iterates from p*p to n, which takes O((n-srt+1)*log(log(n))) time. Therefore, the overall time complexity of this code is O((n-srt+1)*log(log(n))).
Auxiliary Space:
The space complexity of the algorithm is O(n), which is the size of the boolean array prime. However, the size of the array is reduced to n+2-srt, which is the size of the array required for the given range [srt, n]. Therefore, the auxiliary space complexity of the code is O(n-srt+1).
To know more check Sieve of Eratosthenes.
Optimized Sieve of Eratosthenes Method: (Bitwise Sieve Method)
One optimization of the above method is, we have skipped all even numbers altogether. We reduce the size of the prime array to half. We also reduce all iterations to half.
Below is the implementation:
Python3
def bitwiseSieve(srt, n):
prime = [0]*int(n / 2);
if (srt%2 == 0):
srt += 1
if(srt <= 2):
srt = 3
i = srt
while(i * i < n):
if (prime[int(i / 2)] == 0):
j = i * i;
while(j < n):
prime[int(j / 2)] = 1;
j += i * 2;
i += 2;
print(2,end=" ");
i = 3;
while(i < n):
if (prime[int(i / 2)] == 0):
print(i,end=" ");
i += 2;
if __name__=='__main__':
srt = 1
end = 10
bitwiseSieve(srt, end)
Time Complexity: O(n*log(log n)), where n is the difference between the intervals.
Space Complexity: O(n)
Last Updated :
04 May, 2023
Like Article
Save Article
Простое число — это натуральное число, которое больше 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 вместе с вами, читаю, собираю и записываю информацию опытных программистов.
Алгоритм нахождения простых чисел
Время на прочтение
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