Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Prime number - Conditional expression in For loop

Posted on 2011-09-19
7
428 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
ID: 36564857
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
ID: 36564874
The following link explains what JAGRUT_PATEL has explained
http://en.wikipedia.org/wiki/Prime_number
0
 
LVL 15

Expert Comment

by:navneethegde
ID: 36564892
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
Master Your Team's Linux and Cloud Stack

Come see why top tech companies like Mailchimp and Media Temple use Linux Academy to build their employee training programs.

 
LVL 37

Accepted Solution

by:
TommySzalapski earned 300 total points
ID: 36569256
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
ID: 36569268
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
ID: 36569274
Oops. It's C#. Math.Sqrt is correct, not #include<cmath>
0
 

Author Closing Comment

by:IzzyTwinkly
ID: 36570206
Thanks guys~
It was a big help!!!
0

Featured Post

Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
Calculating holidays and working days is a function that is often needed yet it is not one found within the Framework. This article presents one approach to building a working-day calculator for use in .NET.
The Email Laundry PDF encryption service allows companies to send confidential encrypted  emails to anybody. The PDF document can also contain attachments that are embedded in the encrypted PDF. The password is randomly generated by The Email Laundr…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

856 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