0
How is the square root of the key to the sieve of eratosthenes and finding prime numbers?
Wiki User
∙ 11y ago
If you are trying to find a factor of a number n, then there is no need to search beyond s = sqrt(n). For if a factor of n is greater than s, then its factor pair will be less than s and so you should have found that already.
For proof, let u be the factor pair. That is, t*u = n. Also s*s = n so that t*u = s*s
Divide both sides by u*s so that t/s = s/u
Now, t > s implies that t/s > 1 and so s/u > 1 which means that s > u.
Wiki User
∙ 9y ago
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.
How did Eratosthenes invent prime numbers?
Prime numbers are not invented.
When did Eratosthenes find prime numbers?
Eratosthenes lived between 276 and 194 B.C. He didn't discover prime numbers; he devised a simple way to determine what numbers are prime in a given range.
How many even prime numbers are there in a sieve of Eratosthenes?
One
What did eratosthenes devise for locating with relative efficiency prime numbers?
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'.
What is the name of Eratosthenes method of finding prime numbers?
It is called a sieve.
Who is the founder of prime numbers?
Eratosthenes, It says it is Eratosthenes.
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.
How did Eratosthenes invent prime numbers?
Prime numbers are not invented.
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.
How was the Mathematician who found a very simple method for finding the prime and composite numbers in the third century BC?
Eratosthenes
When did Eratosthenes find prime numbers?
Eratosthenes lived between 276 and 194 B.C. He didn't discover prime numbers; he devised a simple way to determine what numbers are prime in a given range.
Did eratosthenes make a mistake in prime numbers?
The algorithm for identifying prime numbers which is known as the Sieve of Eratosthenes has been accepted as accurate for thousands of years.
What did the sieve of Eratosthenes used to find?
prime numbers
What does the prime number graph invented by Eratosthenes look like?
it looks like a 100 square grid with 1 to 100 and you highlight all the prime numbers
Who was the mathematician who suggested a simple method for finding the prime numbers up to a given natural number?
The method of sieving the multiples of prime numbers until only the prime numbers remain, while attributed to Eratosthenes, is originally thought to have been the work of Nicomachus.
