To extend the Sieve of Eratosthenes to 200, what is the largest prime whose multiples would have to be considered?

Question

Efrain Tapia

Mathematics

18 November, 20:40

To extend the Sieve of Eratosthenes to 200, what is the largest prime whose multiples would have to be considered?

+3

Answers (1)

Know the Answer?

Noe Bradshaw · Answer 1

The largest prime that needs to be checked for factors of a number n is floor (sqrt (n)), or |sqrt (n) | in some notations, meaning the largest integer that does not exceed sqrt (n).

For example, if checking 169, whose squre-root is 13. There will be NO prime factors below 13 (1 is not a prime). So check for all prime factors up to and including the largest prime equal to or less than sqrt (n).