+ 3

Why do we have the limit as half of the number to check whether the no is prime or not?

in for loop used in this program

19th Dec 2017, 3:01 PM
Subha
Subha - avatar
2 Réponses
+ 4
It is to reduce the computation time. In order to determine whether a number is prime you have to see whether it is divisible by any number.i.e. see whether it has any factors. except one and itself. The way to find factors are by dividing the number being checked by all numbers smaller than itself. example 12 12 ÷ 1 = 12 12 ÷ 2 = 6 12 ÷ 3 = 4 12 ÷ 4 = 3 12 ÷ 5 = 2.something 12 ÷ 6 = 2 12 ÷ 7 = 1.something from 7 onwards are all 1.something so you can see that from above half of 12 i.e six up you are wasting your time doing calculations trying to find factors. So by doing calculation from 2 up to 12/2 you are saving calculation time. The optimal is actually up to sqrt(12).
20th Dec 2017, 3:41 AM
Louis
Louis - avatar
0
If it is not a prime, it has to be the product of two numbers. z=a*b The smallest factor is 2. So the other number must be smaller than z/2. Otherwise the result would be larger than z. You can test the rest of the numbers. It's just useless.
19th Dec 2017, 7:22 PM
1of3
1of3 - avatar