# Prime number - Conditional expression in For loop

Hi,

This program is created to find the prime numbers between 2 and 20.
inside the second for loop, the conditional statement is i <= num/2.
why do we use this as our conditional statement?

int factor;
bool isPrime;

for (int num = 2; num < 20; num++)
{
isPrime = true;
factor = 0;
Console.WriteLine("num " + num);
// see if num is evenly divisible.
for (int i = 2; i <= num/2; i++)
{
Console.WriteLine("i: " + i + " num/2: " + num/2 + " num%2 " + num%i);
if ((num % i) == 0)
{
// num is evenly divisible.  Thus, it is not prime.
isPrime = false;
factor = i;
}
Console.WriteLine("factor: " + factor);
}

if (isPrime)
Console.WriteLine(num + " is prime.");
else
Console.WriteLine("Largest factor of " + num + " is " + factor);
###### Who is Participating?

x

Commented:
It's just poorly programmed.
You don't need to bother checking anything past num/2 because no numbers in that range can be factors of num.

As jagrut_patel mentioned, all you need to do is check every number i = 2; i <= sqrt(num); i++
Since if any number greater than sqrt(num) is a factor of num, then it's other factor is smaller.

For example, if num == 100, then sqrt(100) == 10. 25 is a factor of 100, but 4*25 == 100 so as long as you check 4, you are good. It's easy to prove mathematically that sqrt(num) is the upper bound of what you need to check.
0

Commented:
It is a "trial division" approach of finding prime numbers. I cannot answer why num/2 but instead of "num/2" if we can even use "Math.Sqrt(num)". Thus, inner for loop will have lesser iterations.
Of course, there might be other efficient methods available which I am not aware of.
0

Technical ManagerCommented:
The following link explains what JAGRUT_PATEL has explained
http://en.wikipedia.org/wiki/Prime_number
0

Software EngineerCommented:
Hi!

The Inner for loop
1. Starting from 2, for values from 2 to 19 from outer loop.

If value/2 is less than equal to 2 then loop around the 'inner for'
2. Inner looping then will check if it's divisible by 2, if yes then it's not a prime.
3. If it's not then it's a prime, no looping.

Thanks!
0

Commented:
So they tried to save time by only going up to num/2 but they could have saved more time by only going up to sqrt(num)

By the way, in order to use sqrt, you probably need to use #include<cmath>
0

Commented:
Oops. It's C#. Math.Sqrt is correct, not #include<cmath>
0

Author Commented:
Thanks guys~
It was a big help!!!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.