I need help understanding this program

Please support our C++ advertiser: Intel Parallel Studio Home
Thread Solved

Join Date: Oct 2009
Posts: 6
Reputation: fragtech is an unknown quantity at this point 
Solved Threads: 0
fragtech fragtech is offline Offline
Newbie Poster

I need help understanding this program

 
0
  #1
Oct 27th, 2009
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.

  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. }
Reply With Quote Quick reply to this message  
Join Date: Mar 2008
Posts: 675
Reputation: Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold 
Solved Threads: 100
Sky Diploma's Avatar
Sky Diploma Sky Diploma is offline Offline
Practically a Master Poster
 
3
  #2
Oct 27th, 2009
Well this program is not as complex as it seems to be.

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

Hope this has helped you
1. Please Mark Your Thread as Solved After Getting Your Answers.
2. Please Use CODE TAGS .
Reply With Quote Quick reply to this message  
Join Date: Dec 2008
Posts: 1,344
Reputation: firstPerson is just really nice firstPerson is just really nice firstPerson is just really nice firstPerson is just really nice firstPerson is just really nice 
Solved Threads: 167
firstPerson's Avatar
firstPerson firstPerson is offline Offline
Nearly a Posting Virtuoso
 
0
  #3
Oct 27th, 2009
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 :
  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.
1) What word becomes shorter if you add a letter to it? 
      [ Solved by : niek_e, Paul Thompson, SgtMe, murtan, xavier666, jonsca]
2) What does this sequence  equal to :  (.5u - .5a)(.5u-.5b)(.5u-.5c) ...
      [*solved by : murtan, xavier666]
3) What is the 123456789th prime numer?
Reply With Quote Quick reply to this message  
Join Date: Oct 2009
Posts: 6
Reputation: fragtech is an unknown quantity at this point 
Solved Threads: 0
fragtech fragtech is offline Offline
Newbie Poster
 
0
  #4
Oct 27th, 2009
That helps a lot, but i have one more question. After the second for loop there is
  1. if((i%j) == 0) isprime = false;

Is this the same a saying
  1. for(j=2; j<=i/2; j++) {
  2. if((i%j) == 0) isprime = false;
  3. }
Reply With Quote Quick reply to this message  
Join Date: Mar 2008
Posts: 675
Reputation: Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold Sky Diploma is a splendid one to behold 
Solved Threads: 100
Sky Diploma's Avatar
Sky Diploma Sky Diploma is offline Offline
Practically a Master Poster
 
0
  #5
Oct 27th, 2009
Originally Posted by fragtech View Post
That helps a lot, but i have one more question. After the second for loop there is
  1. if((i%j) == 0) isprime = false;

Is this the same a saying
  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.

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

  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
1. Please Mark Your Thread as Solved After Getting Your Answers.
2. Please Use CODE TAGS .
Reply With Quote Quick reply to this message  
Join Date: Oct 2009
Posts: 6
Reputation: fragtech is an unknown quantity at this point 
Solved Threads: 0
fragtech fragtech is offline Offline
Newbie Poster
 
0
  #6
Oct 27th, 2009
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.
Reply With Quote Quick reply to this message  
Join Date: Dec 2008
Posts: 1,344
Reputation: firstPerson is just really nice firstPerson is just really nice firstPerson is just really nice firstPerson is just really nice firstPerson is just really nice 
Solved Threads: 167
firstPerson's Avatar
firstPerson firstPerson is offline Offline
Nearly a Posting Virtuoso
 
0
  #7
Oct 27th, 2009
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.
1) What word becomes shorter if you add a letter to it? 
      [ Solved by : niek_e, Paul Thompson, SgtMe, murtan, xavier666, jonsca]
2) What does this sequence  equal to :  (.5u - .5a)(.5u-.5b)(.5u-.5c) ...
      [*solved by : murtan, xavier666]
3) What is the 123456789th prime numer?
Reply With Quote Quick reply to this message  
Reply

This thread has been marked solved.
Perhaps start a new thread instead?
Message:


Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC