Posted by **Emmy** on Friday, October 15, 2010 at 6:08pm.

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 -
**MathMate**, Friday, October 15, 2010 at 8:15pm
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

## Related Questions

- math - Can someone help me with prime and composite numbers? Prime numbers are ...
- math - how to use hundreds chart to answer this;(1)what % of the numbers are ...
- math - if you have 3 rows and three columns and you have to find the hidden ...
- Grade 8 Math - URGENT HELP!Squares into Primes Some primes can be expressed as ...
- Numbers - How many positive integers less than or equal to 1000 are common ...
- Maths - is it possible to find a sequence with the ruleadd four for wich all ...
- Math - 48,24,6,36,12,54 Which of the following describe this set. A. Numbers ...
- algebra - Find all sets of three consecutive multiples of 11 for which the sum ...
- Math - List the common multiples from 1 to 100 for each pair of numbers. Then ...
- math - A set of 100 open lockers are numbered from 1 - 100. Sarah comes by and ...

More Related Questions