Checking all the integers in the range [1, n - 1] is not efficient. Think about a better approach.

Since most of the numbers are not primes, we need a fast approach to exclude the non-prime integers.

Use Sieve of Eratosthenes.