Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- tri = NewType('tri', Optional[bool])
- class prime_numbers:
- prime_naturals_oeis40: Tuple[int, ...] = (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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
- 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271) # https://oeis.org/A000040
- __primes: Deque[int] | Tuple[int, ...] = deque(prime_naturals_oeis40)
- __max_p_tmp: int = max(__primes) # enables efficient resumes of searching in edit mode
- @classmethod
- def freeze_primes(cls, get_freeze_unfreeze: tri) -> tri:
- """ This method allows the user to "freeze" or "unfreeze" the __primes attribute. When frozen, __primes is converted to a tuple (immutable), and when unfrozen, it's converted back to a deque (mutable).
- The method returns the current state (True for unfrozen, False for frozen, or None for an error). """
- if get_freeze_unfreeze is None: # get
- return isinstance(cls.__primes, deque)
- elif get_freeze_unfreeze is False: # freeze
- try:
- cls.__primes = tuple(cls.__primes)
- return False
- except MemoryError:
- return isinstance(cls.__primes, deque)
- elif get_freeze_unfreeze is True: # unfreeze
- try:
- cls.__primes = deque(cls.__primes)
- return True
- except MemoryError:
- return isinstance(cls.__primes, deque)
- range_spec_tuple_t = NewType('range_spec_tuple_t', Tuple[int] | Tuple[int, int] | Tuple[int, int, int])
- @classmethod
- def gen_primes_sieve_1_resumable(cls, output_wanted: range_spec_tuple_t, below: Optional[int] = None, above: Optional[int] = None, max_look_ahead: Optional[int] = None, edit: bool = False) -> Iterable[Optional[Tuple[int, int]]]:
- """
- Generate prime numbers in a resumable manner using a simple trial division method.
- Parameters:
- - output_wanted (range_spec_tuple_t): A tuple specifying the range of prime numbers desired.
- - below (Optional[int]): An optional integer specifying the upper limit for the prime numbers.
- - above (Optional[int]): An optional integer specifying the lower limit for the prime numbers.
- - max_look_ahead (Optional[int]): An optional integer specifying the maximum number of primes to look ahead in one search.
- - edit (bool): A boolean indicating whether to edit the list of known primes or not.
- Returns:
- Iterable[Optional[Tuple[int, int]]]: An iterable of optional tuples, where each tuple contains a prime number and its position in __primes if it's in the desired output range.
- Functionality:
- 1. If `edit` is True, the method attempts to find new prime numbers by checking if they are divisible by any of the known primes. If a new prime is found, it's appended to the __primes list.
- 2. If `edit` is False, the method checks if the last known prime is within the specified range. If not, it yields None and returns.
- 3. The method then iterates through the known primes and yields those that are within the specified range, along with their positions.
- 4. Finally, the method yields None to indicate the end of the sequence.
- 5. In edit mode, the progress of the search is saved. So, search can be chunked by the `max_look_ahead`.
- """
- primes = cls.__primes
- rso = range(*output_wanted)
- above: int = above or (min(rso) - 1)
- below: int = below or (max(rso) + 1)
- max_look_ahead: int = max_look_ahead or (len(rso) + 1)
- del rso
- if edit:
- attempt: int = 0
- for attempt in range(max(primes[-1] + 2, cls.__max_p_tmp), min(below, above + max_look_ahead), 2):
- if not any(attempt % x == 0 for x in primes):
- primes.append(attempt)
- if attempt != 0:
- cls.__max_p_tmp = attempt
- del attempt
- elif primes[-1] > below or primes[-1] < above:
- yield None
- return
- else:
- if above <= below or below < 2:
- yield None
- return
- ipi = enumerate(primes)
- oro = range(*output_wanted)
- for pid, x in ipi:
- if x > above:
- if x in oro:
- yield x, pid
- break
- for pid, x in ipi:
- if x >= below:
- break
- if x in oro:
- yield x, pid
- yield None
- return
- @classmethod
- def gen_primes_sieve_2_eratosthenes(cls, output_wanted: range_spec_tuple_t, below: Optional[int] = None, above: Optional[int] = None, max_look_ahead: Optional[int] = None) -> Iterable[int]:
- """ Generate prime numbers using the Sieve of Eratosthenes algorithm. """
- oro = range(*output_wanted)
- start, stop, step = oro.start, oro.stop, oro.step
- # Ensure the range is valid
- if start > stop:
- return iter([]) # Return an empty iterator
- # If the range is within the already known primes
- if start <= cls.__primes[-1]:
- for prime in cls.__primes:
- if start <= prime <= stop:
- yield prime
- return
- # Determine the range for the sieve based on the provided parameters
- sieve_start = above or start
- sieve_end = below or max(stop, cls.__primes[-1] ** 2)
- if max_look_ahead:
- sieve_end = min(sieve_end, sieve_start + max_look_ahead)
- sieve = [True] * (sieve_end + 1)
- for prime in cls.__primes:
- for multiple in range(max(2 * prime, sieve_start), sieve_end + 1, prime):
- sieve[multiple] = False
- # Generate new primes and add them to __primes
- for num in range(max(2, sieve_start), sieve_end + 1):
- if sieve[num]:
- cls.__primes.append(num)
- if start <= num <= stop:
- yield num
- @classmethod
- def can_check_sieve(cls, nr: range_spec_tuple_t) -> tri:
- range_object = range(*nr)
- if range_object:
- return cls.__primes[-1] ** 2 > max(range_object)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement