Advertisement
banovski

Prime numbers in a range

Nov 7th, 2022 (edited)
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 5.51 KB | Source Code | 0 0
  1. #! /usr/bin/env python3
  2.  
  3. the_number = 10000
  4.  
  5. def check_with_prime_list(max_number):
  6.     prime_numbers = [2, 3, 5]
  7.  
  8.     for subset_start in range(7, max_number, 10):
  9.         for checked_number in range(subset_start, subset_start + 7, 2):
  10.             for prime in prime_numbers:
  11.                 if checked_number % prime == 0:
  12.                     break
  13.             else:
  14.                 prime_numbers.append(checked_number)
  15.  
  16.     while prime_numbers[-1] > max_number:
  17.         prime_numbers.pop(-1)
  18.  
  19.     return prime_numbers
  20.  
  21. # one = check_with_prime_list(the_number)
  22. # 1230 function calls in 0.104 seconds
  23.  
  24. def sieve_of_eratosthenes(max_number):
  25.     # Cоздаем список натуральных чисел: ко второму аргументу функции
  26.     # range добавляем единицу здесь и далее, потому что иначе она
  27.     # формирует последовательность до значения второго аргумента не
  28.     # включительно.
  29.     natural_numbers_list = [i for i in range(2, max_number + 1)]
  30.     # Перебираем множители, которые будут использоваться для
  31.     # "вычеркивания" их произведений: так как максимальный множитель
  32.     # дающий произведение, не выходящее за пределы последовательности
  33.     # в два раза меньше ее максимального значения, то для указания
  34.     # верхней границы диапазона используется целочисленное деление на
  35.     # два.
  36.     for factor in range(2, max_number // 2 + 1):
  37.         # Превращаем множители в их произведения, а затем -- в индексы
  38.         # элементов исходного массива, являющихся их произведениями;
  39.         # чтобы не происходило "вычеркивание" самих множителей, часть
  40.         # из которых является простыми числами, последовательность
  41.         # произведений начинается с произведения множителя и двойки.
  42.         for index in range(factor * 2, max_number + 1, factor):
  43.             # Так как сгенерированный список натуральных чисел
  44.             # начинается с двойки, а индексация списка с нуля, это
  45.             # учитывается при формировании значения индекса;
  46.             # "вычеркиванием" является перезапись элемента исходного
  47.             # списка двойкой, дубликатом значения, которое и так
  48.             # должно быть в результирующем списке; потом дубликаты
  49.             # будут удалены и останется только одна двойка.
  50.             natural_numbers_list[index - 2] = 2
  51.            
  52.     # Превращаем список во множество из-за чего из него удаляются
  53.     # дубликаты. Насколько я знаю, это популярный среди питонистов
  54.     # трюк.
  55.     prime_numbers = set(natural_numbers_list)
  56.     # Так как множества -- это неупорядоченные коллекции, сортируем
  57.     # полученное множество, одновременно превращая его в список. Так
  58.     # как set и sorted -- низкоуровневые функции, заменять их
  59.     # самописным кодом для повышения производительности смысла нет.
  60.     return sorted(prime_numbers)
  61.  
  62. # two = sieve_of_eratosthenes(the_number)
  63. # 6 function calls in 0.020 seconds
  64.  
  65. def is_prime(num):
  66.     if num == 2 or num == 5:
  67.         return True
  68.     else:
  69.         if num < 2 or num % 5 == 0 or num % 2 == 0:
  70.             return False
  71.  
  72.     i = 3
  73.     while i < num:
  74.         if num % i == 0:
  75.             return False
  76.         i += 2
  77.         if i % 5 == 0:
  78.             i += 2
  79.  
  80.     return True
  81.  
  82. def get_primes_with_loop(n):
  83.     primes = list()
  84.     for i in range(n):
  85.         if is_prime(i):
  86.             primes.append(i)
  87.  
  88.     return primes
  89.  
  90. # get_primes_with_loop(the_number)
  91. # 10004 function calls in 1.022 seconds
  92.  
  93. def get_primes_like_erathosphenes(n):
  94.     primes = list()
  95.     primes.append(2)
  96.     marks = [True for i in range(n + 1)]
  97.    
  98.     i = 3
  99.     while i * i <= n:
  100.         if marks[i]:
  101.             j = i * i
  102.             while j < n:
  103.                 marks[j] = False
  104.                 j += i
  105.         i += 2
  106.  
  107.     i = 3
  108.    
  109.     while i <= n:
  110.         if marks[i]:
  111.             primes.append(i)
  112.         i += 2
  113.  
  114.     return primes
  115.  
  116. # get_primes_like_erathosphene(the_number)
  117. # 1234 function calls in 0.005 seconds
  118.  
  119. def get_primes_truncate_multiples(max):
  120.     multiples = set()
  121.     upper_limit = max + 1
  122.     all = set(range(3, upper_limit, 2))
  123.     multiples = {(i * j)
  124.                  for i in range(2, upper_limit)
  125.                  for j in range(2, upper_limit // i)}
  126.  
  127.     return sorted(all.difference(multiples))
  128.  
  129. # get_primes_truncate_multiples(the_number)
  130. # 7 function calls in 0.020 seconds
  131.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement