Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #! /usr/bin/env python3
- the_number = 10000
- def check_with_prime_list(max_number):
- prime_numbers = [2, 3, 5]
- for subset_start in range(7, max_number, 10):
- for checked_number in range(subset_start, subset_start + 7, 2):
- for prime in prime_numbers:
- if checked_number % prime == 0:
- break
- else:
- prime_numbers.append(checked_number)
- while prime_numbers[-1] > max_number:
- prime_numbers.pop(-1)
- return prime_numbers
- # one = check_with_prime_list(the_number)
- # 1230 function calls in 0.104 seconds
- def sieve_of_eratosthenes(max_number):
- # Cоздаем список натуральных чисел: ко второму аргументу функции
- # range добавляем единицу здесь и далее, потому что иначе она
- # формирует последовательность до значения второго аргумента не
- # включительно.
- natural_numbers_list = [i for i in range(2, max_number + 1)]
- # Перебираем множители, которые будут использоваться для
- # "вычеркивания" их произведений: так как максимальный множитель
- # дающий произведение, не выходящее за пределы последовательности
- # в два раза меньше ее максимального значения, то для указания
- # верхней границы диапазона используется целочисленное деление на
- # два.
- for factor in range(2, max_number // 2 + 1):
- # Превращаем множители в их произведения, а затем -- в индексы
- # элементов исходного массива, являющихся их произведениями;
- # чтобы не происходило "вычеркивание" самих множителей, часть
- # из которых является простыми числами, последовательность
- # произведений начинается с произведения множителя и двойки.
- for index in range(factor * 2, max_number + 1, factor):
- # Так как сгенерированный список натуральных чисел
- # начинается с двойки, а индексация списка с нуля, это
- # учитывается при формировании значения индекса;
- # "вычеркиванием" является перезапись элемента исходного
- # списка двойкой, дубликатом значения, которое и так
- # должно быть в результирующем списке; потом дубликаты
- # будут удалены и останется только одна двойка.
- natural_numbers_list[index - 2] = 2
- # Превращаем список во множество из-за чего из него удаляются
- # дубликаты. Насколько я знаю, это популярный среди питонистов
- # трюк.
- prime_numbers = set(natural_numbers_list)
- # Так как множества -- это неупорядоченные коллекции, сортируем
- # полученное множество, одновременно превращая его в список. Так
- # как set и sorted -- низкоуровневые функции, заменять их
- # самописным кодом для повышения производительности смысла нет.
- return sorted(prime_numbers)
- # two = sieve_of_eratosthenes(the_number)
- # 6 function calls in 0.020 seconds
- def is_prime(num):
- if num == 2 or num == 5:
- return True
- else:
- if num < 2 or num % 5 == 0 or num % 2 == 0:
- return False
- i = 3
- while i < num:
- if num % i == 0:
- return False
- i += 2
- if i % 5 == 0:
- i += 2
- return True
- def get_primes_with_loop(n):
- primes = list()
- for i in range(n):
- if is_prime(i):
- primes.append(i)
- return primes
- # get_primes_with_loop(the_number)
- # 10004 function calls in 1.022 seconds
- def get_primes_like_erathosphenes(n):
- primes = list()
- primes.append(2)
- marks = [True for i in range(n + 1)]
- i = 3
- while i * i <= n:
- if marks[i]:
- j = i * i
- while j < n:
- marks[j] = False
- j += i
- i += 2
- i = 3
- while i <= n:
- if marks[i]:
- primes.append(i)
- i += 2
- return primes
- # get_primes_like_erathosphene(the_number)
- # 1234 function calls in 0.005 seconds
- def get_primes_truncate_multiples(max):
- multiples = set()
- upper_limit = max + 1
- all = set(range(3, upper_limit, 2))
- multiples = {(i * j)
- for i in range(2, upper_limit)
- for j in range(2, upper_limit // i)}
- return sorted(all.difference(multiples))
- # get_primes_truncate_multiples(the_number)
- # 7 function calls in 0.020 seconds
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement