in the sieve of Eratosthenes for numbers less than 100, explain why after we cross our the multiples of 2 3 5 and 7 the remaining numbers are primes.

Answer 1

There is a theorem in number theory that states that if a number n is composite, the smallest prime factor cannot exceed √n.

It is easy to understand if we consider n to be composite, which has to have at least two factors other than 1 or n, and if the smallest factor is greater than √n, then the product of the factors will exceed (√n)² > n.

Using this theorem, the largest prime factor less than √100 is 7 (8,9,10 are composite). So using the sieve, we only need to cross out multiples of prime numbers less than or equal to 10, which is 7.