Find All Primes

# Find All Primes ## Difficulty Easy ## Tags `math`, `sieve of eratosthenes` ## Problem Statement Write a function that returns all prime numbers strictly less than a non-negative integer `n`. ## Constraints - `n` is a non-negative integer. - 0 ≤ n ≤ 10⁶ - Result should be a list of integers in ascending order. ## Signatures ### Python ```python def find_primes(n: int) -> List[int]: pass ``` ### Java ```java public class Solution { public List<Integer> find_primes(int n) { return null; } } ``` ### Csharp ```csharp public class Solution { public IList<int> find_primes(int n) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: vector<int> find_primes(int n) { } }; ``` ### C ```c int* find_primes(int n) { } ``` ### Ruby ```ruby def find_primes(n) end ``` ### Perl ```perl sub find_primes { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def find_primes(n: Int): List[Int] = { } } ``` ### Haskell ```haskell find_primes :: ... -> ... find_primes args = undefined ``` ### Clojure ```clojure (defn find_primes [n] ) ``` ### Scheme ```scheme (define (find_primes n) ) ``` ## Examples ### Example 1 **Input:** ``` n = 10 ``` **Output:** ``` [2, 3, 5, 7] ``` **Explanation:** There are 4 prime numbers less than 10. ### Example 2 **Input:** ``` n = 2 ``` **Output:** ``` [] ``` **Explanation:** No primes less than 2. ### Example 3 **Input:** ``` n = 20 ``` **Output:** ``` [2, 3, 5, 7, 11, 13, 17, 19] ``` **Explanation:** All primes less than 20. ### Example 4 **Input:** ``` n = 0 ``` **Output:** ``` [] ``` **Explanation:** No primes less than 0. ## Hints 1. The naive approach checks divisibility for each number, taking O(n√n). 2. The Sieve of Eratosthenes is more efficient with O(n log log n) time complexity. 3. Create a boolean array marking all numbers as prime, then iteratively mark multiples of each prime as composite.