Решето Аткина

python
  1. import math
  2.  
  3. def AtkinSieve(limit):
  4.     results = [2, 3, 5]
  5.     sieve = [False] * (limit + 1)
  6.     factor = int(math.sqrt(limit)) + 1
  7.     for i in range(1, factor):
  8.         for j in range(1, factor):
  9.             n = 4 * i ** 2 + j ** 2
  10.             if (n <= limit) and (n % 12 == 1 or n % 12 == 5):
  11.                 sieve[n] = not sieve[n]
  12.             n = 3 * i ** 2 + j ** 2
  13.             if (n <= limit) and (n % 12 == 7):
  14.                 sieve[n] = not sieve[n]
  15.             if i > j:
  16.                 n = 3 * i ** 2 - j ** 2
  17.                 if (n <= limit) and (n % 12 == 11):
  18.                     sieve[n] = not sieve[n]
  19.     for index in range(5, factor):
  20.         if sieve[index]:
  21.             for jndex in range(index ** 2, limit, index ** 2):
  22.                 sieve[jndex] = False
  23.     for index in range(7, limit):
  24.         if sieve[index]:
  25.             results.append(index)
  26.     return results
 
Пример использования:
  1. a = AtkinSieve(2000000)
  2.  
  3. for i in range(0, len(a)):
  4.     if (a[i] > 1000000) and (a[i] < 2000000):
  5.         print a[i]
Выводит все простые числа в диапазоне от 1 000 000 до 2 000 000.
Назад

Реклама

Мы в соцсетях

tw tg yt gt