파이썬 소수 필터 함수

Here is a Python function that extracts prime numbers from an unsorted list, optimized for performance without external libraries: ```python def get_primes(numbers): """ Returns a new list containing only the prime numbers from the input list. Optimized for performance using a sieve approach for the maximum value. """ if not numbers: return [] # Find the maximum value in the list to bound the sieve max_val = max(numbers) if max_val < 2: return [] # Sieve of Eratosthenes to mark primes up to max_val sieve = [True] * (max_val + 1) sieve[0] = sieve[1] = False for i in range(2, int(max_val ** 0.5) + 1): if sieve[i]: for j in range(i * i, max_val + 1, i): sieve[j] = False # Filter the original list, preserving order and duplicates return [num for num in numbers if num >= 2 and sieve[num]] ``` **Explanation of optimizations:** 1. **Sieve of Eratosthenes**: Instead of testing each number individually (which would be O(n * sqrt(m))), we precompute all primes up to the maximum value in the list. This reduces the complexity to O(m log log m) for the sieve plus O(n) for filtering, where m is the max value and n is the list length. 2. **Early exit**: If the list is empty or the maximum value is less than 2, we return an empty list immediately. 3. **Memory efficiency**: The sieve uses a boolean list of size max_val + 1, which is efficient for typical integer ranges. 4. **Preserves order and duplicates**: The final list comprehension iterates through the original list, so the output maintains the original order and includes duplicate primes if they appear. **Example usage:** ```python print(get_primes([10, 7, 3, 5, 2, 11, 4, 7])) # Output: [7, 3, 5, 2, 11, 7] print(get_primes([1, 4, 6, 8, 9])) # Output: [] print(get_primes([-5, 0, 2, 3, 5])) # Output: [2, 3, 5] ``` **Performance note**: For very large lists with a high maximum value, this approach is significantly faster than trial division. However, if the list contains extremely large numbers (e.g., > 10^7), the sieve may consume too much memory. In such cases, a hybrid approach using trial division with precomputed small primes could be considered, but for most practical scenarios, this sieve-based method is optimal.