Prime number - Conditional expression in For loop


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.");
   Console.WriteLine("Largest factor of " + num + " is " + factor);
Who is Participating?

Improve company productivity with a Business Account.Sign Up

TommySzalapskiConnect With a Mentor 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.
jagrut_patelConnect With a Mentor 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.
Anurag ThakurConnect With a Mentor Technical ManagerCommented:
The following link explains what JAGRUT_PATEL has explained
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

NavneetSoftware EngineerCommented:

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.

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>
Oops. It's C#. Math.Sqrt is correct, not #include<cmath>
IzzyTwinklyAuthor Commented:
Thanks guys~
It was a big help!!!
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.

All Courses

From novice to tech pro — start learning today.