Post a New Question

Math

posted by .

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.

  • Math -

    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.

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

More Related Questions

Post a New Question