0
Why is the square root the key to the Sieve of Eratosthenes and finding prime numbers?
Wiki User
∙ 12y ago
Let p be the number we are testing for primality.
The reason we don't have to check beyong sqrt(p) is if any number n larger than sqrt(p) divides p, then p/n, which is greater than n, also divides p.
Consider the following example with 101.
We check to see that 2, 3, 5, and 7 do not divide 101.
11*11 = 121 implies 11*X = 101 only if X is smaller than 11. But we already checked the numbers smaller than 11.
Wiki User
∙ 12y ago
The Sieve of Eratosthenes is a method used to find all prime numbers up to a given limit. The square root is utilized in this sieve because if a number has a factor larger than its square root, then it must also have a corresponding factor smaller than its square root. Therefore, by only checking numbers up to the square root of the given limit, we can effectively identify all the prime numbers.
Add your answer:
Earn +20 pts
Why is the prime number grid called the sieve?
One method for finding prime numbers is called the "Sieve of Eratosthenes" because it basically "sifts" through the numbers looking for numbers that are not not prime.
What are you filtering with sieve of eratosthenes?
The Sieve of Eratosthenes filters numbers, letting the composites fall through while the primes remain.
How many even prime numbers are there in a sieve of Eratosthenes?
One
What are the crossed out numbers above one called on a sieve of Eratosthenes?
composite numbers
What did eratosthenes devise for locating with relative efficiency prime numbers?
A sieve.
What is the name of Eratosthenes method of finding prime numbers?
It is called a sieve.
What is the name of Eratosthenes' method of finding composite numbers?
Eratosthenes' method of finding prime and composite number is called 'The Sieve of Eratosthene'.
How many prime numbers are located on sieve of erastosthenes?
The sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to any given limit.
Why is the prime number grid called the sieve?
One method for finding prime numbers is called the "Sieve of Eratosthenes" because it basically "sifts" through the numbers looking for numbers that are not not prime.
What is the definition of the sieve of Eratosthenes in mathematics?
The mathematical term "sieve of Eratosthenes" is defined as a simple algorithm for finding all prime numbers up to a given limit. It is named after a famous Greek mathematician of the same name.
What are you filtering with sieve of eratosthenes?
The Sieve of Eratosthenes filters numbers, letting the composites fall through while the primes remain.
How do you find the greatest common factor of 18 and 54 using the sieve of eratosthenes?
By finding all the factors of the numbers and see which one is the biggest # they have in common. Or look at the Sieve of Eratosthenes table at google.com and there you will find the answer.or by looking at a sieve of Eratosthenes and crossing out the factors of each number and seeing which two factors are the same but the highest out of them both.
What did the sieve of Eratosthenes used to find?
prime numbers
Where did Eratosthenes Sieve invent prime no?
The Sieve did not invent prime numbers. It was used to find them.
How many even prime numbers are there in a sieve of Eratosthenes?
One
What are the crossed out numbers above one called on a sieve of Eratosthenes?
composite numbers
When did Eratosthenes discover the sieve?
The sieve of Eratosthenes was discovered in 223 BC.
