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);
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.
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
The revolutionary project management tool is here! Plan visually with a single glance and make sure your projects get done.
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.
Of course, there might be other efficient methods available which I am not aware of.