+ 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
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).
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.