Post a New Question

Math

posted by on .

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.

Answer This Question

First Name:
School Subject:
Answer:

Related Questions

More Related Questions

Post a New Question