Advertisement
HasteBin0

Python 3 Simple prime_number Class

Oct 2nd, 2023
1,288
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 6.39 KB | None | 0 0
  1.  
  2.  
  3. tri = NewType('tri', Optional[bool])
  4.  
  5.  
  6. class prime_numbers:
  7.     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,
  8.                                               173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271)  # https://oeis.org/A000040
  9.    
  10.     __primes: Deque[int] | Tuple[int, ...] = deque(prime_naturals_oeis40)
  11.     __max_p_tmp: int = max(__primes)  # enables efficient resumes of searching in edit mode
  12.    
  13.     @classmethod
  14.     def freeze_primes(cls, get_freeze_unfreeze: tri) -> tri:
  15.         """ 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).
  16.            The method returns the current state (True for unfrozen, False for frozen, or None for an error). """
  17.         if get_freeze_unfreeze is None:  # get
  18.             return isinstance(cls.__primes, deque)
  19.         elif get_freeze_unfreeze is False:  # freeze
  20.             try:
  21.                 cls.__primes = tuple(cls.__primes)
  22.                 return False
  23.             except MemoryError:
  24.                 return isinstance(cls.__primes, deque)
  25.         elif get_freeze_unfreeze is True:  # unfreeze
  26.             try:
  27.                 cls.__primes = deque(cls.__primes)
  28.                 return True
  29.             except MemoryError:
  30.                 return isinstance(cls.__primes, deque)
  31.    
  32.     range_spec_tuple_t = NewType('range_spec_tuple_t', Tuple[int] | Tuple[int, int] | Tuple[int, int, int])
  33.    
  34.     @classmethod
  35.     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]]]:
  36.         """
  37.        Generate prime numbers in a resumable manner using a simple trial division method.
  38.  
  39.        Parameters:
  40.        - output_wanted (range_spec_tuple_t): A tuple specifying the range of prime numbers desired.
  41.        - below (Optional[int]): An optional integer specifying the upper limit for the prime numbers.
  42.        - above (Optional[int]): An optional integer specifying the lower limit for the prime numbers.
  43.        - max_look_ahead (Optional[int]): An optional integer specifying the maximum number of primes to look ahead in one search.
  44.        - edit (bool): A boolean indicating whether to edit the list of known primes or not.
  45.  
  46.        Returns:
  47.        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.
  48.  
  49.        Functionality:
  50.        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.
  51.        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.
  52.        3. The method then iterates through the known primes and yields those that are within the specified range, along with their positions.
  53.        4. Finally, the method yields None to indicate the end of the sequence.
  54.        5. In edit mode, the progress of the search is saved. So, search can be chunked by the `max_look_ahead`.
  55.        """
  56.         primes = cls.__primes
  57.         rso = range(*output_wanted)
  58.         above: int = above or (min(rso) - 1)
  59.         below: int = below or (max(rso) + 1)
  60.         max_look_ahead: int = max_look_ahead or (len(rso) + 1)
  61.         del rso
  62.         if edit:
  63.             attempt: int = 0
  64.             for attempt in range(max(primes[-1] + 2, cls.__max_p_tmp), min(below, above + max_look_ahead), 2):
  65.                 if not any(attempt % x == 0 for x in primes):
  66.                     primes.append(attempt)
  67.             if attempt != 0:
  68.                 cls.__max_p_tmp = attempt
  69.             del attempt
  70.         elif primes[-1] > below or primes[-1] < above:
  71.             yield None
  72.             return
  73.         else:
  74.             if above <= below or below < 2:
  75.                 yield None
  76.                 return
  77.         ipi = enumerate(primes)
  78.         oro = range(*output_wanted)
  79.         for pid, x in ipi:
  80.             if x > above:
  81.                 if x in oro:
  82.                     yield x, pid
  83.                 break
  84.         for pid, x in ipi:
  85.             if x >= below:
  86.                 break
  87.             if x in oro:
  88.                 yield x, pid
  89.         yield None
  90.         return
  91.    
  92.     @classmethod
  93.     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]:
  94.         """ Generate prime numbers using the Sieve of Eratosthenes algorithm. """
  95.         oro = range(*output_wanted)
  96.         start, stop, step = oro.start, oro.stop, oro.step
  97.        
  98.         # Ensure the range is valid
  99.         if start > stop:
  100.             return iter([])  # Return an empty iterator
  101.        
  102.         # If the range is within the already known primes
  103.         if start <= cls.__primes[-1]:
  104.             for prime in cls.__primes:
  105.                 if start <= prime <= stop:
  106.                     yield prime
  107.             return
  108.        
  109.         # Determine the range for the sieve based on the provided parameters
  110.         sieve_start = above or start
  111.         sieve_end = below or max(stop, cls.__primes[-1] ** 2)
  112.         if max_look_ahead:
  113.             sieve_end = min(sieve_end, sieve_start + max_look_ahead)
  114.        
  115.         sieve = [True] * (sieve_end + 1)
  116.         for prime in cls.__primes:
  117.             for multiple in range(max(2 * prime, sieve_start), sieve_end + 1, prime):
  118.                 sieve[multiple] = False
  119.        
  120.         # Generate new primes and add them to __primes
  121.         for num in range(max(2, sieve_start), sieve_end + 1):
  122.             if sieve[num]:
  123.                 cls.__primes.append(num)
  124.                 if start <= num <= stop:
  125.                     yield num
  126.    
  127.     @classmethod
  128.     def can_check_sieve(cls, nr: range_spec_tuple_t) -> tri:
  129.         range_object = range(*nr)
  130.         if range_object:
  131.             return cls.__primes[-1] ** 2 > max(range_object)
  132.    
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement