Code analysis

[livingsword]

i got this prime no. code for analysis. and i hav not been able to understand it completely.

#include<iostream.h>
  #include<conio.h>
   void main()
   
  {
                  int x, y, c = 0;
                  clrscr();
   
                  cout<<"\nPrime Numbers upto 100 :\n ";
   
                  for( x = 2; x < 100; x++ )
   
                  {
                          if( x % 2 != 0 || x == 2 )
                          {
                                  for( y = 2; y <= x / 2; y++ )
                                  {
                                          if( x % y == 0 )
                                          {
                                                  break;
                                          }
                                  }
   
                                  if( y > x / 2 )
                                  {
                                          cout<<"\n\t" <<x ;
                                          c++;
                                  }
                          }
                  }
   
                  cout<< "\n \nTotal Prime No.: " << c ;
                  getch();
  }

Now, what i understood is that ,

- x is used to generate a list of 100 nos.
- the first 'if' condition is used to select only ODD no.

i really dont get the rest of the program ,

Please help. :-|

thnx for reading the post.

[John A]

Hmm... where did you get the code? 'Cause it looks like it was written for the ancient Turbo compiler. I would suggest finding some better code that does not use old coding methods such as iostream.h (new replacement is simply iostream), clrscr(), void main and getch().

Anyway, regarding the initial question: I'm not terribly good at explaining. Here's how I look at it:

The first if() statement does indeed check to see if the number is odd. The reasoning behind this is because any even number larger than 2 is divisible by 2 and therefore not prime. The second loop simply goes through all the numbers to see if any divide evenly into the first number.

In essence, it's doing something like this:
5

Does 2 go into 5? No.
Does 3 go into 5? No.
Does 4 go into 5? No.
Now we hit 5, and we exit, so it must have been a prime number.

[thekashyap]

#include<iostream.h>
#include<conio.h>
void main()

{
    int x, y, c = 0;
    clrscr();

    cout<<"\nPrime Numbers upto 100 :\n ";

    for( x = 2; x < 100; x++ )
    {
        //check only odd numbers, even are never prime.
        if( x % 2 != 0 || x == 2 )
        {
            //if an odd number 'x' is divisible by any number between 2 and '(int)x/2' then it is NOT a prime number.

            for( y = 2; y <= x / 2; y++ )
            {
                //If 'x' is divisible by any number between 2 and x/2, loop will break BEFORE y is '>' x/2.
                //There is no point checking for numbers greater than x/2 as the possibility  of x being divisible 
                //by numbers greater than x is nil and 
                //by numbers between x and x/2 is same as x/2 and 2.
                 if( x % y == 0 )
                {
                    break;
                }
            }

           //If 'x' is divisible by any number between 2 and x/2, loop will break BEFORE y is '>' x/2.
            if( y > x / 2 )
            {
                cout<<"\n\t" <<x ;
                c++;
            }
        }
    }

    cout<< "\n \nTotal Prime No.: " << c ;
    getch();
}

[Aia]

for( x = 2; x < 100; x++ )

This for loop will start with the value 2 stored in x and
check every time if is less that 100, so it will never reach 100 numbers but 99, since at the 100th time it will quit. After the block {} is executed it will increment x by one, making x = 3 and so on.

if( x % 2 != 0 || x == 2 )

will execute only if: the remainder of the division
between the value of x and 2 is not 0 (zero) OR x is iquals to 2. If one or both of
the operations are true then it will keep going down.

for( y = 2; y <= x / 2; y++ )

similar to the first loop only that is nested inside
the if statement and then subject to it in the execution. Also notice the <=, meaning
that it will check upto the value of x included, not like the first for loop.

if( x % y == 0 )

problably you could figure this one out compering it with the first if.

if( y > x / 2 )

if the value store in y is greater than the result of dividing the
value store in x and 2, then it will execute the following block, which it will make stop the second for loop.

I don't know where you got this "masterpiece of code". But let me tell you before someone does differently. You don't want to emulate these things:

main should always be int and not void.

clrscr()

not need there and should be avoid since makes your code not portable.
same with the use of

#include <conio.h>

. and

getch()

In fact

getch()

is easyly
sustituded for getchar() that is standard.
The indentation is too much.

Check this link for good formatting code

[livingsword]

thnx evry1 for replying,

@ Aia :

i do know some part of code is deprecated. but i dont intent to use it as it is. i need to use the logic.
ur advice is mere translation of the code into english , wich i guess even im capable of doing.

but thnx for sparing time and looking into the code.

@ the kashyap & joeprogrammer :

thnx for ur explanations, it helped, but my doubt remains,

why does 'y' need to be < x/2 ??:-|

it would be gr8 if any1 could giv me a dry-run(say with no. 21) explanation to clear out things.

thnx u all for ur time and effort.

[WaltP]

why does 'y' need to be < x/2 ??:-|

It doesn't, but the smallest prime number is 2, so the largest prime number for n is n/2. Anything >n/2 and <n cannot be a factor of n, so why check above n/2

[~s.o.s~]

You can save iterations and the additional checking performed in the loops by doing something like:

#include <iostream>

int main ()
{
    using namespace std ;

    int limit = -1, count = 1 ;
    bool isPrime = true ;

    cout << "Enter the limit: " ;
    cin >> limit ;
    getchar () ;

    cout << 2 << endl ; // handle special case since 2 is the only even prime number

    // the number of loops are cut in half by the use of i+=2 since
    // only odd numbers can be prime ( except for 2 which is even )
    
    for (int i = 3; i < limit; i+=2)
    {

        // there is a theorem which states that a number if not prime 
       // has to have factors less than equal to its own square root
        for (int j = 2; j * j <= i; ++j)
        {
            if (i % j == 0)
            {
                isPrime = false ;  // since factor found hence not prime
                break ;
            }
        }
        if (isPrime)
        {
            ++count ;
            cout << i << endl ;
        }
        else
        {
            isPrime = true ;  // reset the flag for next number
        }
    }

    cout << "The number of random numbers in the given range are : " << count ;
    getchar () ;
    return 0;
}

[livingsword]

It doesn't, but the smallest prime number is 2, so the largest prime number for n is n/2. Anything >n/2 and <n cannot be a factor of n, so why check above n/2

thnx. but wat beats me is .. what is the need for n/2 ?

why do we need to consider half of the no. to check if its a prime ?:-|

[~s.o.s~]

The n / 2 does not aid in checking for prime numbers. Remove it and you still would get the same answer. It just helps in cutting down extra processing and iterations.

Also read my first post for a better optimization.

[WaltP]

It doesn't, but the smallest prime number is 2, so the largest prime number for n is n/2. Anything >n/2 and <n cannot be a factor of n, so why check above n/2

thnx. but wat beats me is .. what is the need for n/2 ?

why do we need to consider half of the no. to check if its a prime ?:-|

Sheesh! OK, you want to find out if 31 is prime. What's half of 31? 15, rounded down. The next value is 16. Can 16 possibly be a factor of 31? How about 17, 18, 19...? If it's impossible, why check them? Therefore you can stop checking at n/2

[livingsword]

ok. got it .

thnx s.o.s and waltp for explaining it to me.