Solved

# Prime number - Conditional expression in For loop

Posted on 2011-09-19
420 Views
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);
0
Question by:IzzyTwinkly

LVL 8

Assisted Solution

jagrut_patel earned 100 total points
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

LVL 26

Assisted Solution

Anurag Thakur earned 100 total points
The following link explains what JAGRUT_PATEL has explained
http://en.wikipedia.org/wiki/Prime_number
0

LVL 15

Expert Comment

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

LVL 37

Accepted Solution

TommySzalapski earned 300 total points
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

LVL 37

Expert Comment

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

LVL 37

Expert Comment

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

Author Closing Comment

Thanks guys~
It was a big help!!!
0

## Featured Post

### Suggested Solutions

Many of us here at EE write code. Many of us write exceptional code; just as many of us write exception-prone code. As we all should know, exceptions are a mechanism for handling errors which are typically out of our control. From database errors, t…
For those of you who don't follow the news, or just happen to live under rocks, Microsoft Research released a beta SDK (http://www.microsoft.com/en-us/download/details.aspx?id=27876) for the Xbox 360 Kinect. If you don't know what a Kinect is (http:…
In this tutorial you'll learn about bandwidth monitoring with flows and packet sniffing with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're interested in additional methods for monitoring bandwidt…
This video demonstrates how to create an example email signature rule for a department in a company using CodeTwo Exchange Rules. The signature will be inserted beneath users' latest emails in conversations and will be displayed in users' Sent Items…