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);
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.