I need help understanding this program

[fragtech]

In my c++ book they give a program that finds the prime numbers between 1 and 100. The problem I am having trouble understanding is the logic of the second for loop. I know what it does but not how, if that makes any sense.

#include <iostream>
using namespace std;

int main()
{
  int i, j;
  bool isprime;
  
  for(i=1; i<=100; i++)
  {
    isprime = true;

    // see if the number is evenly divisible
    for(j=2; j<=i/2; j++)
    // if is is, it is not prime
    if((i%j) == 0) isprime = false;

    if(isprime)
     cout << i << " is prime.\n"
  }

  return 0;
}

[Sky Diploma]

Well this program is not as complex as it seems to be.

for(i=1; i<=100; i++)

The first for loop runs from 0 to 100, and runs a test for checking whether its prime or not.

Then in the second for loop.

for(j=2; j<=i/2; j++)

We now start the test at the individual level.
Our basic idea is to check if the number is divisible by any other number which is less than it. if it is divisible by a particular number it is not prime. Else it is.

The logic in j<=i/2 is that a numbers factor cannot be greater than the number divided by 2.

For eg: consider the number 16.
If we divide it by 2 , we get 8.
Now let us see the factors of 16.

1 , 2 ,4,8. But there are no other numbers that are greater than 16/2 as factors. That is the basic logic.

then the next line

if((i%j) == 0) isprime = false;

the % operator gives the remainder of division of the L.H.S with the R.H.S

So why are we interested in the remainder.
This is where we apply the concept that a factor of a number x, divides the number completely... so there is no remainder.
So basically the line says
If the remainder after dividing is 0, then set isprime=false.

After this we have the next line.

if(isprime)

This seems to be confusing . but C/C++ syntax allows such writing. You can see the above code as this

if ( isprime != 0 )

or

if ( isprime != false )

then you cout<< the number. or else continue to the next statement.

Hope this has helped you :)

[mrnutty]

Look up the definition of a prime number, and you will see that
it is a number that can only be divisible evenly by itself and 1.

For example , 3 is a prime number because 3 can only be divided by its
self(3) and 1, without having any remainder left over,
3/3 = 1 remainder 0
3/2 is a decimal number
3/1 = 1 which is a whole number, with remainder 0

Now lets see what the loop does :

for(i=1; i<=100; i++) //starts from 1 to 100, i is used as the number to see if its prime
  {
    isprime = true; //say i is a prime for now
 
    // see if the number is evenly divisible
    for(j=2; j<=i/2; j++) // j starts from 2 to i/2 because every number above i/2 is divisible by i 
    // if is is, it is not prime
    if((i%j) == 0) isprime = false; //check is evenly divisible any other number, i.e check if i / j = a whole number, if so then it is a not a prime
 
    if(isprime)
     cout << i << " is prime.\n"
  }

Read up on prime then you will get this algo.

[fragtech]

That helps a lot, but i have one more question. After the second for loop there is

if((i%j) == 0) isprime = false;

Is this the same a saying

for(j=2; j<=i/2; j++) {
  if((i%j) == 0) isprime = false;
}

[Sky Diploma]

That helps a lot, but i have one more question. After the second for loop there is

if((i%j) == 0) isprime = false;

Is this the same a saying

for(j=2; j<=i/2; j++) {
  if((i%j) == 0) isprime = false;
}

Yes, its a mere notational advantage .
This applies to both for loops and if statements.

If the curly braces { } are absent. the loop only executes the next line.

for(j=2; j<=i/2; j++)
  if((i%j) == 0) isprime = false;

This is actually meaning.

for(j=2; j<=i/2; j++)
 {
     if((i%j) == 0)
     {
         isprime = false;
      }
 }

But its rather a notational advantage to write it that way. So its better off that you donot get lost with the corresponding braces :)

Its significane is known when we are programming on a large scale. I presume :)

[fragtech]

Lets say that i = 16. In the second loop j is set to 2. 16 % 2 == 0 so is prime is false but then j is incremented to 3. 16 % 3 == 1 so is prime is set to true. which says that 16 is a prime number. What am i missing here because I know 16 isn't a prime number.

[mrnutty]

well it should have a break statement there but, when isPrime is set
to false in the loop, no matter what it will come out as false because its not being set true inside the loop, its only being set to false. So it wouldn't matter after it finds its first factor.