DiTo97 · August 25, 2024 01:06 · Aug 25, 2024 · May 4, 2024 · May 4, 2024 · May 4, 2024
diff --git a/~plotting.py b/~plotting.py
@@ -9,7 +9,7 @@ class Tracker(typing.TypedDict):
     space: list[float]
 
 
-def plot_measure_efficiency(N: list[int], efficiency: dict[str, Tracker]):-> None
+def plot_measure_efficiency(N: list[int], efficiency: dict[str, Tracker]):
     """plots the elapsed and space efficiency of multiple configurations"""
     plt.figure(figsize=(12, 6))
 

diff --git a/~profiling.py b/~profiling.py
@@ -1,10 +1,11 @@
+import time
 import typing
 from typing import Any
 
 from memory_profiler import memory_usage
 
 
-def measure(closure: typing.Callable[[...], Any], *args: Any, **kwargs: Any) -> tuple[float, float]:
+def measure(closure: typing.Callable[..., Any], *args: Any, **kwargs: Any) -> tuple[float, float]:
     """measures the elapsed and space efficiency of a closure"""
     start = time.perf_counter()
     space = memory_usage((closure, args, kwargs), interval=0.1, max_usage=True)

diff --git a/!primefinding.py b/!primefinding.py
@@ -116,6 +116,6 @@ def segmented_sieve_of_eratosthenes(n: int) -> list[int]:
 
 
 def mixed_sieve(n: int) -> list[int]:
-    """A prime finding algorithm mixed via rule-of-thumb"""
+    """prime finding algorithm mixed via rule-of-thumb"""
     if n < 1_000: return sieve_of_atkin(n)
     return sieve_of_eratosthenes(n)
diff --git a/~__main__.py b/~__main__.py
@@ -1,6 +1,6 @@
 from tqdm.auto import tqdm
 
-from plotting import plot_timespace_efficiency
+from plotting import plot_measure_efficiency
 from primefinding import (
     sieve_of_eratosthenes, 
     segmented_sieve_of_eratosthenes, 
@@ -14,16 +14,16 @@ def main():
     M = [sieve_of_eratosthenes, segmented_sieve_of_eratosthenes, sieve_of_atkin, mixed_sieve]
     N = list(range(10, 1_000_000_000, 10))
 
-    efficiency = {closure.__name__: {"timeset": [], "spaceset": []} for closure in M}
+    efficiency = {closure.__name__: {"elapsed": [], "space": []} for closure in M}
 
     for n in tqdm(N, desc="prime finding"):
         for closure in M:
-            elapsed, usage = measure(closure, n)
+            elapsed, space = measure(closure, n)
 
-            efficiency[closure.__name__]["timeset"].append(elapsed)
-            efficiency[closure.__name__]["spaceset"].append(usage)
+            efficiency[closure.__name__]["elapsed"].append(elapsed)
+            efficiency[closure.__name__]["space"].append(space)
 
-    plot_timespace_efficiency(N, efficiency)
+    plot_measure_efficiency(N, efficiency)
 
 
 if __name__ == "__main__":

diff --git a/~plotting.py b/~plotting.py
@@ -4,31 +4,31 @@
 
 
 class Tracker(typing.TypedDict):
-    """A time and space efficiency tracker for single configuration"""
-    timeset: list[float]
-    spaceset: list[float]
+    """elapsed and space efficiency tracker for single configuration"""
+    elapsed: list[float]
+    space: list[float]
 
 
-def plot_timespace_efficiency(N: list[int], efficiency: dict[str, Tracker]):-> None
-    """It plots the time and space efficiency of multiple configurations"""
+def plot_measure_efficiency(N: list[int], efficiency: dict[str, Tracker]):-> None
+    """plots the elapsed and space efficiency of multiple configurations"""
     plt.figure(figsize=(12, 6))
 
     plt.subplot(1, 2, 1)
 
     for config in efficiency:
-        plt.plot(N, efficiency[config]["timeset"], label=config)
+        plt.plot(N, efficiency[config]["elapsed"], label=config)
 
     plt.xlabel("upper limit")
-    plt.ylabel("time (s)")
+    plt.ylabel("elapsed (s)")
     plt.xscale("log")
     plt.yscale("log")
     plt.legend()
-    plt.title("time efficiency")
+    plt.title("elapsed efficiency")
 
     plt.subplot(1, 2, 2)
 
     for config in efficiency:
-        plt.plot(N, efficiency[config]["spaceset"], label=config)
+        plt.plot(N, efficiency[config]["space"], label=config)
 
     plt.xlabel("upper limit")
     plt.ylabel("space (MiB)")

diff --git a/~profiling.py b/~profiling.py
@@ -5,10 +5,10 @@
 
 
 def measure(closure: typing.Callable[[...], Any], *args: Any, **kwargs: Any) -> tuple[float, float]:
-    """It measures the time and space efficiency of a closure"""
+    """measures the elapsed and space efficiency of a closure"""
     start = time.perf_counter()
-    usage = memory_usage((closure, args, kwargs), interval=0.1, max_usage=True)
+    space = memory_usage((closure, args, kwargs), interval=0.1, max_usage=True)
 
     elapsed = time.perf_counter() - start
 
-    return elapsed, usage
+    return elapsed, space
diff --git a/~profiling.py b/~profiling.py
@@ -4,11 +4,11 @@
 from memory_profiler import memory_usage
 
 
-def measure(closure: typing.Callable[[...], Any], *args: Any, **kwargs: Any):
+def measure(closure: typing.Callable[[...], Any], *args: Any, **kwargs: Any) -> tuple[float, float]:
     """It measures the time and space efficiency of a closure"""
     start = time.perf_counter()
     usage = memory_usage((closure, args, kwargs), interval=0.1, max_usage=True)
 
-    elapsed = time.time() - start
+    elapsed = time.perf_counter() - start
 
     return elapsed, usage
diff --git a/!primefinding.py b/!primefinding.py
@@ -72,7 +72,7 @@ def segmented_sieve_of_eratosthenes(n: int) -> list[int]:
     
     Notes
     -----
-    The algorithm trades space efficiency for time efficiency to the non-segmented algorithm.
+    The algorithm trades time efficiency for space efficiency to the non-segmented algorithm.
     
     References
     ----------

diff --git a/~__main__.py b/~__main__.py
@@ -1,5 +1,6 @@
 from tqdm.auto import tqdm
 
+from plotting import plot_timespace_efficiency
 from primefinding import (
     sieve_of_eratosthenes, 
     segmented_sieve_of_eratosthenes, 
@@ -13,14 +14,14 @@ def main():
     M = [sieve_of_eratosthenes, segmented_sieve_of_eratosthenes, sieve_of_atkin, mixed_sieve]
     N = list(range(10, 1_000_000_000, 10))
 
-    efficiency = {closure.__name__: {"time": [], "space": []} for closure in M}
+    efficiency = {closure.__name__: {"timeset": [], "spaceset": []} for closure in M}
 
     for n in tqdm(N, desc="prime finding"):
         for closure in M:
             elapsed, usage = measure(closure, n)
 
-            efficiency[closure.__name__]["time"].append(elapsed)
-            efficiency[closure.__name__]["space"].append(usage)
+            efficiency[closure.__name__]["timeset"].append(elapsed)
+            efficiency[closure.__name__]["spaceset"].append(usage)
 
     plot_timespace_efficiency(N, efficiency)
 

diff --git a/~plotting.py b/~plotting.py
@@ -1,31 +1,41 @@
+import typing
+
 import matplotlib.pyplot as plt
 
 
-def plot_timespace_efficiency(limits, results):
+class Tracker(typing.TypedDict):
+    """A time and space efficiency tracker for single configuration"""
+    timeset: list[float]
+    spaceset: list[float]
+
+
+def plot_timespace_efficiency(N: list[int], efficiency: dict[str, Tracker]):-> None
     """It plots the time and space efficiency of multiple configurations"""
     plt.figure(figsize=(12, 6))
 
-    print(len(limits), results)
-
     plt.subplot(1, 2, 1)
-    for func in results:
-        plt.plot(limits, results[func]['time'], label=func)
-    plt.xlabel('Limit')
-    plt.ylabel('Time (seconds)')
-    plt.xscale('log')
-    plt.yscale('log')
+
+    for config in efficiency:
+        plt.plot(N, efficiency[config]["timeset"], label=config)
+
+    plt.xlabel("upper limit")
+    plt.ylabel("time (s)")
+    plt.xscale("log")
+    plt.yscale("log")
     plt.legend()
-    plt.title('Time Efficiency')
+    plt.title("time efficiency")
 
     plt.subplot(1, 2, 2)
-    for func in results:
-        plt.plot(limits, results[func]['space'], label=func)
-    plt.xlabel('Limit')
-    plt.ylabel('Space (MiB)')
-    plt.xscale('log')
-    plt.yscale('log')
+
+    for config in efficiency:
+        plt.plot(N, efficiency[config]["spaceset"], label=config)
+
+    plt.xlabel("upper limit")
+    plt.ylabel("space (MiB)")
+    plt.xscale("log")
+    plt.yscale("log")
     plt.legend()
-    plt.title('Space Efficiency')
+    plt.title("space efficiency")
 
     plt.tight_layout()
     plt.show()
diff --git a/~__main__.py b/~__main__.py
@@ -1,21 +1,29 @@
-def main():
-    pass
+from tqdm.auto import tqdm
 
+from primefinding import (
+    sieve_of_eratosthenes, 
+    segmented_sieve_of_eratosthenes, 
+    sieve_of_atkin, 
+    mixed_sieve
+)
+from profiling import measure
 
-if __name__ == "__main__":
-    # Initialize the results
-    results = {
-        'sieve_of_eratosthenes': {'time': [], 'space': []},
-        'sieve_of_atkin': {'time': [], 'space': []},
-        'mixed_sieve': {'time': [], 'space': []},
-        # 'segmented_sieve_of_eratosthenes': {'time': [], 'space': []},  # FIXME: too slow
-    }
 
-    for limit in tqdm(limits):
-        print(f"Computing primes up to {limit}...")
-        for func in [sieve_of_eratosthenes, sieve_of_atkin, mixed_sieve]:
-            elapsed_time, mem_usage = measure(func, limit)
-            results[func.__name__]['time'].append(elapsed_time)
-            results[func.__name__]['space'].append(mem_usage)
+def main():
+    M = [sieve_of_eratosthenes, segmented_sieve_of_eratosthenes, sieve_of_atkin, mixed_sieve]
+    N = list(range(10, 1_000_000_000, 10))
+
+    efficiency = {closure.__name__: {"time": [], "space": []} for closure in M}
 
-    plot_spacetime_efficiency(limits, results)
+    for n in tqdm(N, desc="prime finding"):
+        for closure in M:
+            elapsed, usage = measure(closure, n)
+
+            efficiency[closure.__name__]["time"].append(elapsed)
+            efficiency[closure.__name__]["space"].append(usage)
+
+    plot_timespace_efficiency(N, efficiency)
+
+
+if __name__ == "__main__":
+    main()
diff --git a/!primefinding.py b/!primefinding.py
@@ -8,8 +8,9 @@ def sieve_of_atkin(n: int) -> list[int]:
     ----------
     .. [1] A. O. L. Atkin, D. J. Bernstein, 2003
     """
-    if n < 3: return [2]
-    if n < 5: return [2, 3]
+    if n < 3: return []
+    if n < 4: return [2]
+    if n < 6: return [2, 3]
 
     m = n + 1
     P = [2, 3]
@@ -38,7 +39,7 @@ def sieve_of_atkin(n: int) -> list[int]:
         if sieve[x]:
             z = x**2
 
-            for k in range(z, x + 1, z):
+            for k in range(z, n + 1, z):
                 sieve[k] = False
 
     for x in range(5, n):

diff --git a/!primefinding.py b/!primefinding.py
@@ -79,7 +79,7 @@ def segmented_sieve_of_eratosthenes(n: int) -> list[int]:
        The Segmented Sieve of Eratosthenes and Primes in Arithmetic Progressions to 10^12
     """
     shape = math.isqrt(n) + 1
-    sieve = [True] * upper
+    sieve = [True] * shape
 
     P = []
 

diff --git a/!primefinding.py b/!primefinding.py
@@ -1,36 +1,49 @@
 import math
 
 
-def sieve_of_atkin(limit):
+def sieve_of_atkin(n: int) -> list[int]:
     """The Sieve of Atkin prime finding algorithm, [1]_
     
     References
     ----------
     .. [1] A. O. L. Atkin, D. J. Bernstein, 2003
     """
-    P = [2,3]
-    sieve=[False]*(limit+1)
-
-    sqrt_limit = math.isqrt(limit)
-
-    for x in range(1,sqrt_limit+1):
-        for y in range(1,sqrt_limit+1):
-            h = x ** 2
-            k = y ** 2
-
-            n = 4*h + k
-            if n<=limit and (n%12==1 or n%12==5) : sieve[n] = not sieve[n]
-            n = 3*h+k
-            if n<= limit and n%12==7 : sieve[n] = not sieve[n]
-            n = 3*h - k
-            if x>y and n<=limit and n%12==11 : sieve[n] = not sieve[n]
-    for n in range(5,sqrt_limit):
-        if sieve[n]:
-            z = n ** 2
-            for k in range(z,limit+1,z):
+    if n < 3: return [2]
+    if n < 5: return [2, 3]
+
+    m = n + 1
+    P = [2, 3]
+
+    sieve = [False] * (m)
+    sqrtn = math.isqrt(n)
+
+    for x in range(1, sqrtn + 1):
+        for y in range(1, sqrtn + 1):
+            h = x**2
+            k = y**2
+
+            i = 4 * h + k
+
+            if i < m and (i % 12 == 1 or i % 12 == 5): sieve[i] = not sieve[i]
+
+            i = i - h
+
+            if i < m and i % 12 == 7: sieve[i] = not sieve[i]
+
+            i = i - 2 * k
+
+            if x > y and i < m and i % 12 == 11: sieve[i] = not sieve[i]
+
+    for x in range(5, sqrtn):
+        if sieve[x]:
+            z = x**2
+
+            for k in range(z, x + 1, z):
                 sieve[k] = False
-    for n in range(5,limit):
-        if sieve[n]: P.append(n)
+
+    for x in range(5, n):
+        if sieve[x]: P.append(x)
+
     return P
 
 

diff --git a/!primefinding.py b/!primefinding.py
@@ -1,3 +1,6 @@
+import math
+
+
 def sieve_of_atkin(limit):
     """The Sieve of Atkin prime finding algorithm, [1]_
     
@@ -8,7 +11,7 @@ def sieve_of_atkin(limit):
     P = [2,3]
     sieve=[False]*(limit+1)
 
-    sqrt_limit = int(limit ** 0.5)
+    sqrt_limit = math.isqrt(limit)
 
     for x in range(1,sqrt_limit+1):
         for y in range(1,sqrt_limit+1):
@@ -31,23 +34,26 @@ def sieve_of_atkin(limit):
     return P
 
 
-def sieve_of_eratosthenes(n):
+def sieve_of_eratosthenes(n: int) -> list[int]:
     """The Sieve of Eratosthenes prime finding algorithm, [1]_
 
     References
     ----------
     .. [1] Nicomachus of Gerasa, 2nd c. AD
        Introduction to Arithmetic
     """
-    sieve = [True] * (n+1)
-    for x in range(2, int(n**0.5) + 1):
+    sieve = [True] * (n + 1)
+    sqrtn = math.isqrt(n)
+
+    for x in range(2, sqrtn + 1):
         if sieve[x]:
-            for i in range(x*x, n+1, x):
+            for i in range(x * x, n + 1, x):
                 sieve[i] = False
-    return [i for i in range(2, n) if sieve[i]]
 
+    return [x for x in range(2, n) if sieve[x]]
 
-def segmented_sieve_of_eratosthenes(n):
+
+def segmented_sieve_of_eratosthenes(n: int) -> list[int]:
     """The page-segmented Sieve of Eratosthenes prime finding algorithm, [1]_
     
     Notes
@@ -59,37 +65,43 @@ def segmented_sieve_of_eratosthenes(n):
     .. [1] C. Bays, R. H. Hudson, 1977
        The Segmented Sieve of Eratosthenes and Primes in Arithmetic Progressions to 10^12
     """
-    limit = math.isqrt(n) + 1
-    primes = []
-    sieve = [True] * limit
-    for p in range(2, limit):
-        if sieve[p]:
-            primes.append(p)
-            for i in range(p*p, limit, p):
+    shape = math.isqrt(n) + 1
+    sieve = [True] * upper
+
+    P = []
+
+    for x in range(2, shape):
+        if sieve[x]:
+            P.append(x)
+
+            for i in range(x * x, shape, x):
                 sieve[i] = False
 
-    low_limit = limit
-    while low_limit < n:
-        high_limit = min(low_limit + limit, n)
-        segments = [True] * (high_limit - low_limit)
+    lower = shape
+
+    while lower < n:
+        upper = min(lower + shape, n)
+        segments = [True] * (upper - lower)
 
-        for p in primes:
-            start = max(p*p, (low_limit // p) * p)
-            if start < low_limit:
-                start += p
-            for i in range(start, high_limit, p):
-                segments[i - low_limit] = False
-
-        for i in range(low_limit, high_limit):
-            if segments[i - low_limit]:
-                primes.append(i)
+        for x in P:
+            start = max(x * x, (lower // x) * x)
+
+            if start < lower:
+                start += x
+
+            for i in range(start, upper, x):
+                segments[i - lower] = False
+
+        for x in range(lower, upper):
+            if segments[x - lower]:
+                P.append(x)
 
-        low_limit = high_limit
+        lower = upper
 
-    return primes
+    return P
 
 
-def mixed_sieve(n):
+def mixed_sieve(n: int) -> list[int]:
     """A prime finding algorithm mixed via rule-of-thumb"""
     if n < 1_000: return sieve_of_atkin(n)
     return sieve_of_eratosthenes(n)
diff --git a/~__main__.py b/~__main__.py
@@ -1,3 +1,7 @@
+def main():
+    pass
+
+
 if __name__ == "__main__":
     # Initialize the results
     results = {

diff --git a/~plotting.py b/~plotting.py
@@ -1,7 +1,8 @@
 import matplotlib.pyplot as plt
 
 
-def plot_spacetime_efficiency(limits, results):
+def plot_timespace_efficiency(limits, results):
+    """It plots the time and space efficiency of multiple configurations"""
     plt.figure(figsize=(12, 6))
 
     print(len(limits), results)

diff --git a/~profiling.py b/~profiling.py
@@ -1,8 +1,14 @@
+import typing
+from typing import Any
+
 from memory_profiler import memory_usage
 
 
-def measure(func, *args, **kwargs):
-    start_time = time.time()
-    mem_usage = memory_usage((func, args, kwargs), interval=0.1, max_usage=True)
-    elapsed_time = time.time() - start_time
-    return elapsed_time, mem_usage
+def measure(closure: typing.Callable[[...], Any], *args: Any, **kwargs: Any):
+    """It measures the time and space efficiency of a closure"""
+    start = time.perf_counter()
+    usage = memory_usage((closure, args, kwargs), interval=0.1, max_usage=True)
+
+    elapsed = time.time() - start
+
+    return elapsed, usage
diff --git a/!primefinding.py b/!primefinding.py
@@ -1,4 +1,10 @@
 def sieve_of_atkin(limit):
+    """The Sieve of Atkin prime finding algorithm, [1]_
+    
+    References
+    ----------
+    .. [1] A. O. L. Atkin, D. J. Bernstein, 2003
+    """
     P = [2,3]
     sieve=[False]*(limit+1)
 
@@ -26,6 +32,13 @@ def sieve_of_atkin(limit):
 
 
 def sieve_of_eratosthenes(n):
+    """The Sieve of Eratosthenes prime finding algorithm, [1]_
+
+    References
+    ----------
+    .. [1] Nicomachus of Gerasa, 2nd c. AD
+       Introduction to Arithmetic
+    """
     sieve = [True] * (n+1)
     for x in range(2, int(n**0.5) + 1):
         if sieve[x]:
@@ -35,6 +48,17 @@ def sieve_of_eratosthenes(n):
 
 
 def segmented_sieve_of_eratosthenes(n):
+    """The page-segmented Sieve of Eratosthenes prime finding algorithm, [1]_
+    
+    Notes
+    -----
+    The algorithm trades space efficiency for time efficiency to the non-segmented algorithm.
+    
+    References
+    ----------
+    .. [1] C. Bays, R. H. Hudson, 1977
+       The Segmented Sieve of Eratosthenes and Primes in Arithmetic Progressions to 10^12
+    """
     limit = math.isqrt(n) + 1
     primes = []
     sieve = [True] * limit
@@ -66,5 +90,6 @@ def segmented_sieve_of_eratosthenes(n):
 
 
 def mixed_sieve(n):
-    if n < 10_000: return sieve_of_atkin(n)
+    """A prime finding algorithm mixed via rule-of-thumb"""
+    if n < 1_000: return sieve_of_atkin(n)
     return sieve_of_eratosthenes(n)
diff --git a/primefinding.py → !primefinding.py b/primefinding.py → !primefinding.py
diff --git a/__main__.py → ~__main__.py b/__main__.py → ~__main__.py
diff --git a/plotting.py → ~plotting.py b/plotting.py → ~plotting.py
diff --git a/profiling.py → ~profiling.py b/profiling.py → ~profiling.py
diff --git a/requirements.txt → ~requirements.txt b/requirements.txt → ~requirements.txt
diff --git a/__main__.py b/__main__.py
@@ -0,0 +1,17 @@
+if __name__ == "__main__":
+    # Initialize the results
+    results = {
+        'sieve_of_eratosthenes': {'time': [], 'space': []},
+        'sieve_of_atkin': {'time': [], 'space': []},
+        'mixed_sieve': {'time': [], 'space': []},
+        # 'segmented_sieve_of_eratosthenes': {'time': [], 'space': []},  # FIXME: too slow
+    }
+
+    for limit in tqdm(limits):
+        print(f"Computing primes up to {limit}...")
+        for func in [sieve_of_eratosthenes, sieve_of_atkin, mixed_sieve]:
+            elapsed_time, mem_usage = measure(func, limit)
+            results[func.__name__]['time'].append(elapsed_time)
+            results[func.__name__]['space'].append(mem_usage)
+
+    plot_spacetime_efficiency(limits, results)
diff --git a/plotting.py b/plotting.py
@@ -0,0 +1,30 @@
+import matplotlib.pyplot as plt
+
+
+def plot_spacetime_efficiency(limits, results):
+    plt.figure(figsize=(12, 6))
+
+    print(len(limits), results)
+
+    plt.subplot(1, 2, 1)
+    for func in results:
+        plt.plot(limits, results[func]['time'], label=func)
+    plt.xlabel('Limit')
+    plt.ylabel('Time (seconds)')
+    plt.xscale('log')
+    plt.yscale('log')
+    plt.legend()
+    plt.title('Time Efficiency')
+
+    plt.subplot(1, 2, 2)
+    for func in results:
+        plt.plot(limits, results[func]['space'], label=func)
+    plt.xlabel('Limit')
+    plt.ylabel('Space (MiB)')
+    plt.xscale('log')
+    plt.yscale('log')
+    plt.legend()
+    plt.title('Space Efficiency')
+
+    plt.tight_layout()
+    plt.show()
diff --git a/primefinding.py b/primefinding.py
@@ -0,0 +1,70 @@
+def sieve_of_atkin(limit):
+    P = [2,3]
+    sieve=[False]*(limit+1)
+
+    sqrt_limit = int(limit ** 0.5)
+
+    for x in range(1,sqrt_limit+1):
+        for y in range(1,sqrt_limit+1):
+            h = x ** 2
+            k = y ** 2
+
+            n = 4*h + k
+            if n<=limit and (n%12==1 or n%12==5) : sieve[n] = not sieve[n]
+            n = 3*h+k
+            if n<= limit and n%12==7 : sieve[n] = not sieve[n]
+            n = 3*h - k
+            if x>y and n<=limit and n%12==11 : sieve[n] = not sieve[n]
+    for n in range(5,sqrt_limit):
+        if sieve[n]:
+            z = n ** 2
+            for k in range(z,limit+1,z):
+                sieve[k] = False
+    for n in range(5,limit):
+        if sieve[n]: P.append(n)
+    return P
+
+
+def sieve_of_eratosthenes(n):
+    sieve = [True] * (n+1)
+    for x in range(2, int(n**0.5) + 1):
+        if sieve[x]:
+            for i in range(x*x, n+1, x):
+                sieve[i] = False
+    return [i for i in range(2, n) if sieve[i]]
+
+
+def segmented_sieve_of_eratosthenes(n):
+    limit = math.isqrt(n) + 1
+    primes = []
+    sieve = [True] * limit
+    for p in range(2, limit):
+        if sieve[p]:
+            primes.append(p)
+            for i in range(p*p, limit, p):
+                sieve[i] = False
+
+    low_limit = limit
+    while low_limit < n:
+        high_limit = min(low_limit + limit, n)
+        segments = [True] * (high_limit - low_limit)
+
+        for p in primes:
+            start = max(p*p, (low_limit // p) * p)
+            if start < low_limit:
+                start += p
+            for i in range(start, high_limit, p):
+                segments[i - low_limit] = False
+
+        for i in range(low_limit, high_limit):
+            if segments[i - low_limit]:
+                primes.append(i)
+
+        low_limit = high_limit
+
+    return primes
+
+
+def mixed_sieve(n):
+    if n < 10_000: return sieve_of_atkin(n)
+    return sieve_of_eratosthenes(n)
diff --git a/profiling.py b/profiling.py
@@ -0,0 +1,8 @@
+from memory_profiler import memory_usage
+
+
+def measure(func, *args, **kwargs):
+    start_time = time.time()
+    mem_usage = memory_usage((func, args, kwargs), interval=0.1, max_usage=True)
+    elapsed_time = time.time() - start_time
+    return elapsed_time, mem_usage
diff --git a/requirements.txt b/requirements.txt
@@ -0,0 +1,3 @@
+matplotlib
+memory-profiler
+tqdm