Commits

Tetsuya Morimoto  committed 8fba4a5

added the sieve of eratosthenes implementations

  • Participants
  • Parent commits 6ddcd79

Comments (0)

Files changed (11)

File eratosthenes/eratosthenes.py

+# -*- coding: utf-8 -*-
+
+__all__ = [
+    "sieve_of_eratosthenes",
+    "is_prime",
+]
+
+def sieve_of_eratosthenes(max_num: int) -> list:
+    """
+    >>> sieve_of_eratosthenes(1)
+    [2]
+    >>> sieve_of_eratosthenes(3)
+    [2, 3]
+    >>> sieve_of_eratosthenes(30)
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    """
+    primes = [2]
+    search_list = range(3, max_num + 1)
+    while search_list and pow(primes[-1], 2) <= search_list[-1]:
+        search_list = [num for num in search_list if num % primes[-1]]
+        primes.append(search_list.pop(0))
+    primes += search_list
+    return primes
+
+def is_prime(num: int) -> bool:
+    """
+    >>> is_prime(3)
+    True
+    >>> is_prime(4)
+    False
+    """
+    return num in sieve_of_eratosthenes(num)

File eratosthenes/eratosthenes_kai.py

+# -*- coding: utf-8 -*-
+
+def sieve_of_eratosthenes(max_num: int) -> list:
+    """
+    >>> sieve_of_eratosthenes(1)
+    []
+    >>> sieve_of_eratosthenes(3)
+    [2, 3]
+    >>> sieve_of_eratosthenes(30)
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    """
+    primes = []
+    search_list = {num: True for num in range(2, max_num + 1)}
+    for num in range(2, max_num + 1):
+        if search_list[num]:
+            for i in range(2 * num, max_num + 1, num):
+                search_list[i] = False
+            primes.append(num)
+    return primes
+
+def is_prime(num: int) -> bool:
+    """
+    >>> is_prime(3)
+    True
+    >>> is_prime(4)
+    False
+    """
+    return num in sieve_of_eratosthenes(num)

File eratosthenes/eratosthenes_kai10.py

+# -*- coding: utf-8 -*-
+
+import os
+import sqlite3
+
+class PrimeList(object):
+
+    db_filename = "/tmp/sqlite3.db"
+
+    def __init__(self):
+        self.db_conn = self._init_db()
+        self.cursor = self.db_conn.cursor()
+
+    def __del__(self):
+        self.db_conn.close()
+
+    def _init_db(self) -> sqlite3.Connection:
+        if os.path.exists(PrimeList.db_filename):
+            os.remove(PrimeList.db_filename)
+        create_table = "CREATE TABLE PRIME (NUM INTEGER PRIMARY KEY);"
+        conn = sqlite3.connect(PrimeList.db_filename)
+        conn.executescript(create_table)
+        return conn
+
+    def get(self, num: int) -> int:
+        self.cursor.execute("SELECT NUM FROM PRIME WHERE NUM = ?", (num,))
+        row = self.cursor.fetchone()
+        return row[0] if row else -1
+
+    def get_all(self) -> tuple:
+        self.cursor.execute("SELECT NUM FROM PRIME ORDER BY NUM")
+        for row in self.cursor.fetchall():
+            yield row[0]
+
+    def set(self, num: int) -> bool:
+        try:
+            self.cursor.execute("INSERT INTO PRIME (NUM) VALUES (?)", (num,))
+            self.db_conn.commit()
+        except Exception as err:
+            print(err)
+            return False
+        return True
+
+class SearchList(object):
+
+    def __init__(self):
+        self.prime_list = PrimeList()
+
+    def add_prime(self, num):
+        self.prime_list.set(num)
+
+    def __getitem__(self, num):
+        for p in self.prime_list.get_all():
+            if num % p == 0:
+                return False
+        return True
+
+def sieve_of_eratosthenes(max_num: int) -> list:
+    """
+    >>> list(sieve_of_eratosthenes(1))
+    []
+    >>> list(sieve_of_eratosthenes(3))
+    [2, 3]
+    >>> list(sieve_of_eratosthenes(30))
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    """
+    search_list = SearchList()
+    _max_num = max_num + 1
+    for num in range(2, _max_num):
+        if search_list[num]:
+            search_list.add_prime(num)
+            yield num
+        if pow(num, 2) > _max_num:
+            for i in range(num + 1, _max_num):
+                if search_list[i]:
+                    yield i
+            break
+
+def is_prime(num: int) -> bool:
+    """
+    >>> is_prime(3)
+    True
+    >>> is_prime(4)
+    False
+    """
+    return num in sieve_of_eratosthenes(num)

File eratosthenes/eratosthenes_kai2.py

+# -*- coding: utf-8 -*-
+
+def sieve_of_eratosthenes(max_num: int) -> list:
+    """
+    >>> sieve_of_eratosthenes(1)
+    []
+    >>> sieve_of_eratosthenes(3)
+    [2, 3]
+    >>> sieve_of_eratosthenes(30)
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    """
+    primes = []
+    search_list = [True for num in range(max_num + 1)]
+    for num in range(2, max_num + 1):
+        if search_list[num]:
+            for i in range(2 * num, max_num + 1, num):
+                search_list[i] = False
+            primes.append(num)
+    return primes
+
+def is_prime(num: int) -> bool:
+    """
+    >>> is_prime(3)
+    True
+    >>> is_prime(4)
+    False
+    """
+    return num in sieve_of_eratosthenes(num)

File eratosthenes/eratosthenes_kai3.py

+# -*- coding: utf-8 -*-
+
+def sieve_of_eratosthenes(max_num: int) -> list:
+    """
+    >>> sieve_of_eratosthenes(1)
+    []
+    >>> sieve_of_eratosthenes(3)
+    [2, 3]
+    >>> sieve_of_eratosthenes(30)
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    """
+    primes = []
+    search_list = [True for num in range(max_num + 1)]
+    for num in range(2, max_num + 1):
+        if search_list[num]:
+            for i in range(2 * num, max_num + 1, num):
+                search_list[i] = False
+            primes.append(num)
+        if pow(num, 2) > max_num:
+            others = [i for i in range(num + 1, max_num + 1) if search_list[i]]
+            primes += others
+            break
+    return primes
+
+def is_prime(num: int) -> bool:
+    """
+    >>> is_prime(3)
+    True
+    >>> is_prime(4)
+    False
+    """
+    return num in sieve_of_eratosthenes(num)

File eratosthenes/eratosthenes_kai4.py

+# -*- coding: utf-8 -*-
+
+def sieve_of_eratosthenes(max_num: int) -> list:
+    """
+    >>> sieve_of_eratosthenes(1)
+    []
+    >>> sieve_of_eratosthenes(3)
+    [2, 3]
+    >>> sieve_of_eratosthenes(30)
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    """
+    primes = []
+    _max_num = max_num + 1
+    search_list = [True for num in range(_max_num)]
+    for num in range(2, _max_num):
+        if search_list[num]:
+            for i in range(2 * num, _max_num, num):
+                search_list[i] = False
+            primes.append(num)
+        if pow(num, 2) > _max_num:
+            others = [i for i in range(num + 1, _max_num) if search_list[i]]
+            primes += others
+            break
+    return primes
+
+def is_prime(num: int) -> bool:
+    """
+    >>> is_prime(3)
+    True
+    >>> is_prime(4)
+    False
+    """
+    return num in sieve_of_eratosthenes(num)

File eratosthenes/eratosthenes_kai5.py

+# -*- coding: utf-8 -*-
+
+import sqlite3
+from contextlib import contextmanager
+
+DB_FILENAME = "/tmp/sqlite3.db"
+DB_CONN = sqlite3.connect(DB_FILENAME)
+
+
+@contextmanager
+def query_prime(num: int) -> int:
+    cursor = DB_CONN.cursor()
+    cursor.execute("SELECT NUM, RESULT FROM PRIME WHERE NUM = :num")
+    row = cursor.fetchone()
+    yield row
+
+def get_prime(num: int) -> int:
+    with query_prime(num) as row:
+        return row["RESULT"]
+
+class CACHE(object):
+    cache = []
+    def __call__(self, max_num): pass
+
+def sieve_of_eratosthenes(max_num: int) -> list:
+    """
+    >>> sieve_of_eratosthenes(1)
+    []
+    >>> sieve_of_eratosthenes(3)
+    [2, 3]
+    >>> sieve_of_eratosthenes(30)
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    """
+    primes = []
+    _max_num = max_num + 1
+    search_list = [True for num in range(_max_num)]
+    for num in range(2, _max_num):
+        if search_list[num]:
+            for i in range(2 * num, _max_num, num):
+                search_list[i] = False
+            primes.append(num)
+        if pow(num, 2) > _max_num:
+            others = [i for i in range(num + 1, _max_num) if search_list[i]]
+            primes += others
+            break
+    return primes
+
+def is_prime(num: int) -> bool:
+    """
+    >>> is_prime(3)
+    True
+    >>> is_prime(4)
+    False
+    """
+    return num in sieve_of_eratosthenes(num)

File eratosthenes/eratosthenes_kai6.py

+# -*- coding: utf-8 -*-
+
+def sieve_of_eratosthenes(max_num: int) -> list:
+    """
+    >>> sieve_of_eratosthenes(1)
+    []
+    >>> sieve_of_eratosthenes(3)
+    [2, 3]
+    >>> sieve_of_eratosthenes(30)
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    """
+    primes = []
+    search_list = {}
+    _max_num = max_num + 1
+    for num in range(2, _max_num):
+        if search_list.get(num) is None:
+            search_list[num] = True
+            for i in range(2 * num, _max_num, num):
+                search_list[i] = False
+            primes.append(num)
+        if pow(num, 2) > _max_num:
+            others = [i for i in range(num + 1, _max_num) if search_list.get(i) is None]
+            primes += others
+            break
+    return primes
+
+def is_prime(num: int) -> bool:
+    """
+    >>> is_prime(3)
+    True
+    >>> is_prime(4)
+    False
+    """
+    return num in sieve_of_eratosthenes(num)

File eratosthenes/eratosthenes_kai7.py

+# -*- coding: utf-8 -*-
+
+def sieve_of_eratosthenes(max_num: int) -> list:
+    """
+    >>> list(sieve_of_eratosthenes(1))
+    []
+    >>> list(sieve_of_eratosthenes(3))
+    [2, 3]
+    >>> list(sieve_of_eratosthenes(30))
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    """
+    search_list = {}
+    _max_num = max_num + 1
+    for num in range(2, _max_num):
+        if search_list.get(num) is None:
+            for i in range(2 * num, _max_num, num):
+                search_list[i] = False
+            yield num
+        if pow(num, 2) > _max_num:
+            for i in range(num + 1, _max_num):
+                if search_list.get(i) is None:
+                    yield i
+            break
+
+def is_prime(num: int) -> bool:
+    """
+    >>> is_prime(3)
+    True
+    >>> is_prime(4)
+    False
+    """
+    return num in sieve_of_eratosthenes(num)

File eratosthenes/eratosthenes_kai8.py

+# -*- coding: utf-8 -*-
+
+class SearchList(object):
+    def __init__(self):
+        self.primes = []
+
+    def add_prime(self, num):
+        self.primes.append(num)
+
+    def __getitem__(self, index):
+        for p in self.primes:
+            if index % p == 0:
+                return False
+        return True
+
+def sieve_of_eratosthenes(max_num: int) -> list:
+    """
+    >>> list(sieve_of_eratosthenes(1))
+    []
+    >>> list(sieve_of_eratosthenes(3))
+    [2, 3]
+    >>> list(sieve_of_eratosthenes(30))
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    """
+    search_list = SearchList()
+    _max_num = max_num + 1
+    for num in range(2, _max_num):
+        if search_list[num]:
+            search_list.add_prime(num)
+            yield num
+        if pow(num, 2) > _max_num:
+            for i in range(num + 1, _max_num):
+                if search_list[i]:
+                    yield i
+            break
+
+def is_prime(num: int) -> bool:
+    """
+    >>> is_prime(3)
+    True
+    >>> is_prime(4)
+    False
+    """
+    return num in sieve_of_eratosthenes(num)

File eratosthenes/eratosthenes_kai9.py

+# -*- coding: utf-8 -*-
+
+from itertools import tee
+
+class SearchList(object):
+    def __init__(self, max_num):
+        self.prime_filter = filter(None, range(2, max_num))
+
+    def is_prime(self, num):
+        pfilter, bkup = tee(self.prime_filter)
+        self.prime_filter = filter(lambda x: x % num, bkup)
+        return num in pfilter
+
+    def get_not_filtered(self, num):
+        for p in filter(lambda x: x > num, self.prime_filter):
+            yield p
+
+def sieve_of_eratosthenes(max_num: int) -> list:
+    """
+    >>> list(sieve_of_eratosthenes(1))
+    []
+    >>> list(sieve_of_eratosthenes(3))
+    [2, 3]
+    >>> list(sieve_of_eratosthenes(30))
+    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
+    """
+    _max_num = max_num + 1
+    search_list = SearchList(_max_num)
+    for num in range(2, _max_num):
+        if search_list.is_prime(num):
+            yield num
+        if pow(num, 2) > _max_num:
+            for p in search_list.get_not_filtered(num):
+                yield p
+            break
+
+def is_prime(num: int) -> bool:
+    """
+    >>> is_prime(3)
+    True
+    >>> is_prime(4)
+    False
+    """
+    return num in sieve_of_eratosthenes(num)