944,220 Members | Top Members by Rank

Ad:
  • C++ Discussion Thread
  • Marked Solved
  • Views: 667
  • C++ RSS
Oct 27th, 2009
0

I need help understanding this program

Expand Post »
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.

C++ Syntax (Toggle Plain Text)
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6. int i, j;
  7. bool isprime;
  8.  
  9. for(i=1; i<=100; i++)
  10. {
  11. isprime = true;
  12.  
  13. // see if the number is evenly divisible
  14. for(j=2; j<=i/2; j++)
  15. // if is is, it is not prime
  16. if((i%j) == 0) isprime = false;
  17.  
  18. if(isprime)
  19. cout << i << " is prime.\n"
  20. }
  21.  
  22. return 0;
  23. }
Similar Threads
Reputation Points: 10
Solved Threads: 0
Newbie Poster
fragtech is offline Offline
14 posts
since Oct 2009
Oct 27th, 2009
3
Re: I need help understanding this program
Well this program is not as complex as it seems to be.

C++ Syntax (Toggle Plain Text)
  1. 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.
C++ Syntax (Toggle Plain Text)
  1. 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
C++ Syntax (Toggle Plain Text)
  1. 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.
C++ Syntax (Toggle Plain Text)
  1. if(isprime)
This seems to be confusing . but C/C++ syntax allows such writing. You can see the above code as this
C++ Syntax (Toggle Plain Text)
  1. if ( isprime != 0 )
or
C++ Syntax (Toggle Plain Text)
  1. if ( isprime != false )
then you cout<< the number. or else continue to the next statement.

Hope this has helped you
Reputation Points: 673
Solved Threads: 125
Practically a Posting Shark
Sky Diploma is offline Offline
818 posts
since Mar 2008
Oct 27th, 2009
0
Re: I need help understanding this program
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 :
C++ Syntax (Toggle Plain Text)
  1. for(i=1; i<=100; i++) //starts from 1 to 100, i is used as the number to see if its prime
  2. {
  3. isprime = true; //say i is a prime for now
  4.  
  5. // see if the number is evenly divisible
  6. for(j=2; j<=i/2; j++) // j starts from 2 to i/2 because every number above i/2 is divisible by i
  7. // if is is, it is not prime
  8. 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
  9.  
  10. if(isprime)
  11. cout << i << " is prime.\n"
  12. }

Read up on prime then you will get this algo.
Reputation Points: 840
Solved Threads: 594
Senior Poster
firstPerson is offline Offline
3,865 posts
since Dec 2008
Oct 27th, 2009
0
Re: I need help understanding this program
That helps a lot, but i have one more question. After the second for loop there is
C++ Syntax (Toggle Plain Text)
  1. if((i%j) == 0) isprime = false;

Is this the same a saying
C++ Syntax (Toggle Plain Text)
  1. for(j=2; j<=i/2; j++) {
  2. if((i%j) == 0) isprime = false;
  3. }
Reputation Points: 10
Solved Threads: 0
Newbie Poster
fragtech is offline Offline
14 posts
since Oct 2009
Oct 27th, 2009
0
Re: I need help understanding this program
Click to Expand / Collapse  Quote originally posted by fragtech ...
That helps a lot, but i have one more question. After the second for loop there is
C++ Syntax (Toggle Plain Text)
  1. if((i%j) == 0) isprime = false;

Is this the same a saying
C++ Syntax (Toggle Plain Text)
  1. for(j=2; j<=i/2; j++) {
  2. if((i%j) == 0) isprime = false;
  3. }
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.

C++ Syntax (Toggle Plain Text)
  1. for(j=2; j<=i/2; j++)
  2. if((i%j) == 0) isprime = false;
This is actually meaning.

C++ Syntax (Toggle Plain Text)
  1. for(j=2; j<=i/2; j++)
  2. {
  3. if((i%j) == 0)
  4. {
  5. isprime = false;
  6. }
  7. }
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
Reputation Points: 673
Solved Threads: 125
Practically a Posting Shark
Sky Diploma is offline Offline
818 posts
since Mar 2008
Oct 27th, 2009
0
Re: I need help understanding this program
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.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
fragtech is offline Offline
14 posts
since Oct 2009
Oct 27th, 2009
0
Re: I need help understanding this program
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.
Reputation Points: 840
Solved Threads: 594
Senior Poster
firstPerson is offline Offline
3,865 posts
since Dec 2008

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in C++ Forum Timeline: Unrelated function call changes variable values (apparently)
Next Thread in C++ Forum Timeline: Borland Strings





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC