Напишите программу, чтобы составить список всех простых чисел меньше 20. Перед началом важно отметить, что такое простое число. Простое число должно быть положительным целым числом, делящимся ровно на 2 целых числа (1 и само по себе) 1 не является простым числом, хотя существует множество различных способов решения этой проблемы, вот несколько различных подходов.
Напишите программу, чтобы составить список всех простых чисел меньше 20.
Прежде чем начать, важно отметить, что такое простое число.
- Простое число должно быть положительным целым числом
- Делится ровно на 2 целых числа (1 и само по себе)
- 1 не является простым числом
Хотя существует множество различных способов решения этой проблемы, вот несколько различных подходов.
Подход 1: Для петель
# Initialize a list primes = [] for possiblePrime in range(2, 21): # Assume number is prime until shown it is not. isPrime = True for num in range(2, possiblePrime): if possiblePrime % num == 0: isPrime = False if isPrime: primes.append(possiblePrime)
Если вы посмотрите на внутренний цикл for, заключенный в красный прямоугольник ниже, обратите внимание, что, как только isPrime имеет значение False, продолжать итерацию неэффективно. Было бы более эффективно выйти из цикла.
7.9 Простые числа. «Поколение Python»: курс для начинающих. Курс Stepik
Подход 2: Для петель с разрывом
Подход 2 более эффективен, чем подход 1, потому что, как только вы обнаружите, что данное число не является простым числом, вы можете выйти из цикла, используя break .
# Initialize a list primes = [] for possiblePrime in range(2, 21): # Assume number is prime until shown it is not. isPrime = True for num in range(2, possiblePrime): if possiblePrime % num == 0: isPrime = False break if isPrime: primes.append(possiblePrime)
Подход 2 гораздо более эффективен, чем подход 1. Например, если вы посмотрите на случай , когда возможное простое число , обратите внимание, что в подходе 2 гораздо меньше итераций.
Подход 3: Для цикла, разрыва и квадратного корня
Подход 2 выиграл от того, что не делал ненужных итераций во внутреннем цикле for. Подход 3 аналогичен, за исключением функции внутреннего диапазона. Обратите внимание, что функция внутреннего диапазона теперь range(2, int(возможное простое число ** 0.5) + 1) .
# Initialize a list primes = [] for possiblePrime in range(2, 21): # Assume number is prime until shown it is not. isPrime = True for num in range(2, int(possiblePrime ** 0.5) + 1): if possiblePrime % num == 0: isPrime = False break if isPrime: primes.append(possiblePrime)
Чтобы объяснить, почему этот подход работает, важно отметить несколько вещей. Составное число-это положительное число, большее 1, которое не является простым (которое имеет факторы , отличные от 1 и самого себя). Каждое составное число имеет коэффициент, меньший или равный его квадратному корню (доказательство здесь ). Например, на изображении факторов 15 ниже обратите внимание, что факторы, выделенные красным цветом, являются просто обратными зеленым факторам. Другими словами, коммутативным свойством умножения 3 x x 3. Вам просто нужно включить зеленые пары, чтобы убедиться, что у вас есть все факторы.
Простые числа (Python)
Сравнение во времени различных подходов
Некоторые методы генерации простых чисел более эффективны. Чтобы показать это, давайте изучим разницу в производительности между подходами, генерирующими простые числа до заданного числа.
Подход 1: Для петель
def approach1(givenNumber): # Initialize a list primes = [] for possiblePrime in range(2, givenNumber + 1): # Assume number is prime until shown it is not. isPrime = True for num in range(2, possiblePrime): if possiblePrime % num == 0: isPrime = False if isPrime: primes.append(possiblePrime) return(primes)
Подход 2: Для петель с разрывом
def approach2(givenNumber): # Initialize a list primes = [] for possiblePrime in range(2, givenNumber + 1): # Assume number is prime until shown it is not. isPrime = True for num in range(2, possiblePrime): if possiblePrime % num == 0: isPrime = False break if isPrime: primes.append(possiblePrime) return(primes)
Подход 3: Для цикла, разрыва и квадратного корня
def approach3(givenNumber): # Initialize a list primes = [] for possiblePrime in range(2, givenNumber + 1): # Assume number is prime until shown it is not. isPrime = True for num in range(2, int(possiblePrime ** 0.5) + 1): if possiblePrime % num == 0: isPrime = False break if isPrime: primes.append(possiblePrime) return(primes)
Разница в производительности может быть измерена с помощью библиотеки timeit , которая позволяет вам синхронизировать код Python. В этом случае мы измеряем время, необходимое для нахождения простых чисел до 500 для каждого подхода. Приведенный ниже код запускает код для каждого подхода 10000 раз и выводит общее время, которое потребовалось в секундах.
import timeit # Approach 1: Execution time print(timeit.timeit(‘approach1(500)’, globals=globals(), number=10000)) # Approach 2: Execution time print(timeit.timeit(‘approach2(500)’, globals=globals(), number=10000)) # Approach 3: Execution time print(timeit.timeit(‘approach3(500)’, globals=globals(), number=10000))
Очевидно, что подход 3 является самым быстрым.
Заключительные замечания
Эти три подхода, безусловно, не являются единственными способами вычисления простых чисел, но, надеюсь, различные способы идентификации простых чисел помогли вам. Простые числа важны в теории чисел и криптографических методах, таких как алгоритм rsa. Как всегда, код в посте также доступен на моем github ( код подхода , сравнение времени ). Если у вас есть какие-либо вопросы или мысли по учебнику, не стесняйтесь обращаться к нам в комментариях ниже или через Twitter .
Эта статья первоначально появилась в моем блоге medium
Читайте ещё по теме:
- Python Factorial | Программа Python для факториала числа
- Программа Python для получения названия Месяца При вводе Номера Пользователем
- Python Program, чтобы найти наименьшее число в списке
- Python Program для генерации случайного количества определенной длины
- Python Program для генерации случайного поплавка
- Python Program, чтобы найти наибольшее количество в списке
- Python – генерировать случайное число – положительный или отрицательный
- Метки approach, interview, number, program, python
Источник: pythobyte.com
unilecs / primeFunc.py
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| # Решение через функциональное программирование |
| def prime_func ( number ): |
| if number < 2 : |
| return False |
| is_delimiter = lambda i : number % i == 0 |
| e = filter ( is_delimiter , range ( 2 , int ( number ** 0.5 + 1 ))) |
| if any ( e ): |
| return False |
| return True |
| # решение через рекурсию |
| def prime_recursion ( number ): |
| def recursion ( n , i ): |
| if n == 2 : |
| return True |
| if n < 2 or n % i == 0 : |
| return False |
| if i in range ( 2 , int ( number ** 0.5 + 1 )): |
| return recursion ( n , i + 1 ) |
| else : |
| return True |
| return recursion ( number , 2 ) |
| def print_is_prime ( number ): |
| if prime_func ( abs ( number )) and prime_recursion ( abs ( number )): |
| print ( «Number <> is prime» . format ( number )) |
| else : |
| print ( «Number <> is NOT prime» . format ( number )) |
| print_is_prime ( 3571 ) |
| # далее тесты |
| # проверка, что обе функции выдают одинаковый результат |
| for n in range ( 1 , 200 ): |
| assert prime_func ( n ) == prime_recursion ( n ), «<>, func — <>, rec — <>» . format ( n , prime_func ( n ), prime_recursion ( n )) |
| # простые числа меньше 200, список с Википедии |
| list_of_primes = [ 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97 , 101 , |
| 103 , 107 , 109 , 113 , 127 , 131 , 137 , 139 , 149 , 151 , 157 , 163 , 167 , 173 , 179 , 181 , 191 , 193 , 197 , 199 ] |
| # дальше генерируем такой же список с помощью наших функций и сравниванием с образцом |
| print ( list ( filter ( prime_func , range ( 1 , 200 )))) |
| print ( list ( filter ( prime_recursion , range ( 1 , 200 )))) |
| print ( list ( filter ( prime_func , range ( 1 , 200 ))) == list_of_primes ) |
| print ( list ( filter ( prime_recursion , range ( 1 , 200 ))) == list_of_primes ) |
Источник: gist.github.com
Python-сообщество
![[RSS Feed]](https://python.su/static/djangobb_forum/img/feed-icon-small.png){kind=icon}
- Начало
- » Python для новичков
- » Вывод перечня простых чисел от 2 до n
#1 Фев. 7, 2015 00:58:28
Вывод перечня простых чисел от 2 до n
Подскажите, пожалуйста, можно ли как-нибудь упростить эту функцию?
def primes(): »’Функция выводит список простых чисел от 2 до n (не включая n)»’ n = int(input(‘Введите число, больше 1: n’)) while n 2: n = int(input(‘Введите число, БОЛЬШЕ 1: n’)) if n == 2: print(‘В диапазоне до 2 нет простых чисел’) else: primes_list = [] for test_number in range(2, n): for num in range(2, test_number): if not test_number % num: break else: continue else: primes_list.append(test_number) primes_list = [str(d) for d in primes_list] print(‘Простые числа в диапазоне до’, n, ‘это -‘, ‘, ‘.join(primes_list))
#2 Фев. 7, 2015 01:50:26
Вывод перечня простых чисел от 2 до n
Найди функцию isprime(), там надо шагать от тройки через один и до корня из числа.
#3 Фев. 7, 2015 02:56:19
Вывод перечня простых чисел от 2 до n
def primes(): »’Функция выводит список простых чисел от 2 до n (не включая n)»’ n = int(input(‘Введите число, больше 1: n’)) while n 2: n = int(input(‘Введите число, БОЛЬШЕ 1: n’)) if n == 2: print(‘В диапазоне до 2 нет простых чисел’) return print(‘Простые числа в диапазоне до %d это — 2’ % n, end=») for test_number in range(3, n): for num in range(2, int(test_number**0.5)+1): if not test_number % num: break else: print(‘, %d’ % test_number, end=») print()
Отредактировано terabayt (Фев. 7, 2015 02:57:39)
#4 Фев. 7, 2015 03:42:17
Вывод перечня простых чисел от 2 до n
for num in range(2, int(test_number**0.5)+1):
Так рассматриваешь числа 4 6 8 … , которые простыми не являются. Поэтому делается шаг через один, чтобы только нечётные проверять.
>>> list(range(3, int(121 ** 0.5) + 1, 2)) [3, 5, 7, 9, 11] >>>
Отредактировано py.user.next (Фев. 7, 2015 03:47:12)
#5 Фев. 7, 2015 03:53:29
Вывод перечня простых чисел от 2 до n
py.user.next
Так рассматриваешь числа 4 6 8 … , которые простыми не являются. Поэтому делается шаг через один, чтобы только нечётные проверять.
ну да, эт хорошая идея!
for test_number in range(3, n, 2): for num in range(3, int(test_number**0.5)+1, 2):
#6 Фев. 7, 2015 06:22:32
Вывод перечня простых чисел от 2 до n
Зачем это упрощать?
Решето Эратосфена или Аткина в помощь.
Отредактировано alekscooper (Фев. 7, 2015 09:59:21)
#7 Фев. 7, 2015 07:50:33
Вывод перечня простых чисел от 2 до n
alekscooper
Зачем это упрощать? Решето Эратосфера или Аткина в помощь.
Stright
можно ли как-нибудь упростить эту функцию?
не просят же подсказать другой алгоритм!
#8 Фев. 7, 2015 09:34:49
Вывод перечня простых чисел от 2 до n
Нашёл тут запись трёхгодичной давности
>>> def prime_range(start, end): . return filter(isprime, range(start, end + 1)) . >>> def isprime(x): . if x > 3 and x % 2 == 0 or x 1: . return False . for i in range(3, int(x ** 0.5) + 1, 2): . if x % i == 0: . return False . return True . >>> n = 1000 >>> print(*prime_range(2, n — 1)) 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 >>>
tags: prime
Отредактировано py.user.next (Окт. 27, 2017 10:49:17)
#9 Фев. 7, 2015 21:14:04
Вывод перечня простых чисел от 2 до n
terabayt
не просят же подсказать другой алгоритм!
А Эратосфен по сути и будет таким упрощением. Обрати внимание, тут уже предложили не проверять чётные числа. Ну а потом можно додуматься уже и до остального.
#10 Фев. 9, 2015 12:49:39
Вывод перечня простых чисел от 2 до n
сть предположение что у тебя падает сессия прежде чем ты успеваешь обработать и ввести данные для входа. Попробуй на zbrowser реализацию сделать или опиши подробнее что необходимо получить.
то что я вижу у тебя 2 раза в коде встречается res = conn.getresponse() и соответственно куки не сохраняются для предыдущий сессии. Или у тебя до этого выпадает ошибка ?
Отредактировано babamithan (Дек. 22, 2015 12:28:02)
- Начало
- » Python для новичков
- » Вывод перечня простых чисел от 2 до n
Источник: python.su