Для начала нам нужно узнать, что такое простое число.
Простое число всегда является положительным целым числом и делится ровно на 2 целых числа (1 и само число), 1 не является простым числом.
Теперь мы обсудим некоторые методы, чтобы найти простое число.
def primemethod1(number): # Initialize a list my_primes = [] for pr in range(2, number): isPrime = True for i in range(2, pr): if pr % i == 0: isPrime = False if isPrime: my_primes.append(pr) print(my_primes) primemethod1(50)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Для петель с перерывом.
def primemethod2(number): # Initialize a list my_primes = [] for pr in range(2, number + 1): isPrime = True for num in range(2, pr): if pr % num == 0: isPrime = False break if isPrime: my_primes.append(pr) return(my_primes) print(primemethod2(50))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
Для петли, разрыва и квадратного корня.
def primemethod3(number): # Initialize a list primes = [] for pr in range(2, number): isPrime = True for num in range(2, int(pr ** 0.5) + 1): if pr % num == 0: isPrime = False break if (isPrime): print(«Prime number: «,pr) primemethod3(50)
Prime number: 2 Prime number: 3 Prime number: 5 Prime number: 7 Prime number: 11 Prime number: 13 Prime number: 17 Prime number: 19 Prime number: 23 Prime number: 29 Prime number: 31 Prime number: 37 Prime number: 41 Prime number: 43 Prime number: 47
Источник: pythononline.ru
Самый быстрый алгоритм поиска делителей числа | Информатика ЕГЭ 2023
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Cancel Create
algorithms-and-data-structures / 4_2 Поиск простых чисел.py /
Code definitions
Code navigation index up-to-date
- Go to file T
- Go to line L
- Go to definition R
- Copy path
- Copy permalink
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Cannot retrieve contributors at this time
150 lines (112 sloc) 5.1 KB
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents Copy raw contents
Copy raw contents
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
| # Написать два алгоритма нахождения 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() |
| # 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() |
| # 1 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:58() |
| # 1 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:61() |
| # 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() |
| # 2 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:58() |
| # 2 0.000 0.000 0.000 0.000 Lesson_4_Task_2.py:61() |
| # Время выполнения нарастает. Рекурсий нет. |
| 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’-ое простое число ‘) |
| # print(‘OK’) |
| # else: |
| # print(‘Ошибка’) |
| # if search_prime(n) == test(n): |
| # print(f’-ое простое число ‘) |
| # print(‘OK’) |
| # else: |
| # print(‘Ошибка’) |
Простые числа. Напишите программу, которая находит все простые числа от a до b включительно | Python
- Copy lines
- Copy permalink
- View git blame
- Reference in new issue
Источник: github.com
Русские Блоги
Несколько методов Python для поиска всех простых чисел в диапазоне (простые числа)
Введение в простые числа
Простые числа также называются простыми числами. Натуральное число больше 1, кроме 1 и самого себя, число, которое не может делиться на другие натуральные числа, называется простым числом; в противном случае оно называется составным числом.
способ 1
def primeNUM(min,max): if min==1: print(») min += 1 for i in range(min, max+1): for j in range(2, i + 1): if i % j == 0: # Судите, могу ли я быть делимым break # Выход из цикла for if j == i: # Если j равно i, i — простое число print(i,end=» «) print(») primeNUM(1,200)
Способ 2
def test(num): list = [] # Определить список для хранения вычисленных чисел i = num -1 # Удалите себя while i > 1: # Удалить 1 if num %i == 0 : # Судите, есть ли остаток list.append(i) # Добавить все числа, которые могут делить i, в список i -= 1 if len(list) == 0 and num != 1: # Если список пуст, это означает, что он делится кроме 1 и самого себя print(num,end=’ ‘) def primeNUM2(min,max): j = min while j max: test(j) j += 1 print(») primeNUM2(1,100)
Источник: russianblogs.com