Celebrate National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Prime number - Conditional expression in For loop

Posted on 2011-09-19
7
Medium Priority
?
447 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
[X]
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
7 Comments
 
LVL 8

Assisted Solution

by:jagrut_patel
jagrut_patel earned 400 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 400 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:Navneet
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 37

Accepted Solution

by:
TommySzalapski earned 1200 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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

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

Wouldn’t it be nice if you could test whether an element is contained in an array by using a Contains method just like the one available on List objects? Wouldn’t it be good if you could write code like this? (CODE) In .NET 3.5, this is possible…
This article shows how to deploy dynamic backgrounds to computers depending on the aspect ratio of display
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…
Visualize your data even better in Access queries. Given a date and a value, this lesson shows how to compare that value with the previous value, calculate the difference, and display a circle if the value is the same, an up triangle if it increased…

730 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