Solved

Prime number - Conditional expression in For loop

Posted on 2011-09-19
7
430 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
How Do You Stack Up Against Your Peers?

With today’s modern enterprise so dependent on digital infrastructures, the impact of major incidents has increased dramatically. Grab the report now to gain insight into how your organization ranks against your peers and learn best-in-class strategies to resolve incidents.

 
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

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

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.

Question has a verified solution.

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

Suggested Solutions

Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
This article aims to explain the working of CircularLogArchiver. This tool was designed to solve the buildup of log file in cases where systems do not support circular logging or where circular logging is not enabled
In an interesting question (https://www.experts-exchange.com/questions/29008360/) here at Experts Exchange, a member asked how to split a single image into multiple images. The primary usage for this is to place many photographs on a flatbed scanner…
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…

740 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