Exploring primality tests and efficient prime generation using sieves like the Sieve of Eratosthenes.
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Prime numbers are the building blocks of integers and are central to number theory and cryptography. A fundamental problem is primality testing: determining whether a given number 'n' is prime. A simple approach is trial division, where we check for divisibility by all integers from 2 up to the square root of 'n'. While easy to implement, this method is too slow for large numbers. More sophisticated probabilistic tests like the Miller-Rabin test are used in practice for large 'n'. Another common task is generating all prime numbers up to a certain limit. The most famous algorithm for this is the Sieve of Eratosthenes. It works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. We create a boolean array, `isPrime`, initialized to true. We start with p=2. If `isPrime[p]` is true, then p is prime, and we mark all multiples of p (2p, 3p, ...) as not prime. We then find the next number greater than p that is not marked and repeat the process. This method is highly efficient for generating primes up to a reasonably large limit (e.g., 10^7).