Solved

Prime number - Conditional expression in For loop

Posted on 2011-09-19
7
420 Views
Last Modified: 2013-12-17
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
Comment
Question by:IzzyTwinkly
7 Comments
 
LVL 8

Assisted Solution

by:jagrut_patel
jagrut_patel earned 100 total points
Comment Utility
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

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

Expert Comment

by:navneethegde
Comment Utility
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
Find Ransomware Secrets With All-Source Analysis

Ransomware has become a major concern for organizations; its prevalence has grown due to past successes achieved by threat actors. While each ransomware variant is different, we’ve seen some common tactics and trends used among the authors of the malware.

 
LVL 37

Accepted Solution

by:
TommySzalapski earned 300 total points
Comment Utility
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

by:TommySzalapski
Comment Utility
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

by:TommySzalapski
Comment Utility
Oops. It's C#. Math.Sqrt is correct, not #include<cmath>
0
 

Author Closing Comment

by:IzzyTwinkly
Comment Utility
Thanks guys~
It was a big help!!!
0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

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…

762 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now