Created
August 13, 2024 03:11
-
-
Save ZhouQiang19980220/cd210d35857a72d200295263c29f04e4 to your computer and use it in GitHub Desktop.
使用埃氏筛法定义一个素数生成器
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ | |
| Generator functions for prime numbers using sieve of Eratosthenes. | |
| """ | |
| from typing import Generator, Optional, Callable | |
| def natural_numbers(start: int = 0, | |
| stop: Optional[int] = None, | |
| step: int = 1) -> Generator[int, None, None]: | |
| """ | |
| Generate an infinite sequence of natural numbers starting from a given start value. | |
| Args: | |
| start (int, optional): The starting value of the sequence. Defaults to 0. | |
| stop (int, optional): The value at which the sequence should stop. Defaults to None. | |
| step (int, optional): The step size between consecutive numbers. Defaults to 1. | |
| Yields: | |
| int: The next natural number in the sequence. | |
| """ | |
| if stop is None: | |
| stop = float('inf') | |
| while start < stop: | |
| yield start | |
| start += step | |
| def not_divisible(x: int) -> Callable[int, bool]: | |
| """ | |
| Returns a function that checks if a given number is not divisible by x. | |
| Parameters: | |
| x (int): The divisor. | |
| Returns: | |
| Callable[int, bool]: A function that takes an integer as input and returns True | |
| if the number is not divisible by x, False otherwise. | |
| """ | |
| def _not_divisible(y: int) -> bool: | |
| return y % x != 0 | |
| return _not_divisible | |
| def prime_numbers() -> Generator[int, None, None]: | |
| """ | |
| Generator function that yields prime numbers. | |
| Returns: | |
| int: The next prime number in the sequence. | |
| Yields: | |
| int: The prime numbers in ascending order. | |
| """ | |
| it = natural_numbers(2) # 初始序列 | |
| while True: | |
| prime = next(it) | |
| yield prime | |
| # 构造新序列：使用 filter() 过滤掉能被 prime 整除的数 | |
| it = filter(not_divisible(prime), it) | |
| if __name__ == '__main__': | |
| import unittest | |
| class TestGenerator(unittest.TestCase): | |
| """ | |
| 测试素数序列 | |
| """ | |
| def test_prime_numbers(self, ): | |
| """ | |
| 测试素数生成器 | |
| """ | |
| correct_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, | |
| 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] | |
| my_prime_numbers = prime_numbers() | |
| while correct_primes: | |
| prime = next(my_prime_numbers) | |
| self.assertEqual(prime, correct_primes.pop(0)) | |
| unittest.main() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment