| | |
I need help understanding this program
Please support our C++ advertiser: Intel Parallel Studio Home
Thread Solved |
•
•
Join Date: Oct 2009
Posts: 6
Reputation:
Solved Threads: 0
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)
#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; }
3
#2 28 Days Ago
Well this program is not as complex as it seems to be.
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.
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
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 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.
This seems to be confusing . but C/C++ syntax allows such writing. You can see the above code as this
or
then you cout<< the number. or else continue to the next statement.
Hope this has helped you
C++ Syntax (Toggle Plain Text)
for(i=1; i<=100; i++)
Then in the second for loop.
C++ Syntax (Toggle Plain Text)
for(j=2; j<=i/2; j++)
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)
if((i%j) == 0) isprime = false;
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)
if(isprime)
C++ Syntax (Toggle Plain Text)
if ( isprime != 0 )
C++ Syntax (Toggle Plain Text)
if ( isprime != false )
Hope this has helped you
0
#3 28 Days Ago
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 :
Read up on prime then you will get this algo.
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)
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.
I give up!
1) What word becomes shorter if you add a letter to it? [ Solved by : niek_e ]
2) What does this sequence equal to : (.5u - .5a)(.5u-.5b)(.5u-.5c) ...
3) What is the 123456789 prime numer?•
•
Join Date: Oct 2009
Posts: 6
Reputation:
Solved Threads: 0
0
#4 28 Days Ago
That helps a lot, but i have one more question. After the second for loop there is
Is this the same a saying
C++ Syntax (Toggle Plain Text)
if((i%j) == 0) isprime = false;
Is this the same a saying
C++ Syntax (Toggle Plain Text)
for(j=2; j<=i/2; j++) { if((i%j) == 0) isprime = false; }
0
#5 28 Days Ago
•
•
•
•
That helps a lot, but i have one more question. After the second for loop there is
C++ Syntax (Toggle Plain Text)
if((i%j) == 0) isprime = false;
Is this the same a saying
C++ Syntax (Toggle Plain Text)
for(j=2; j<=i/2; j++) { if((i%j) == 0) isprime = false; }
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)
for(j=2; j<=i/2; j++) if((i%j) == 0) isprime = false;
C++ Syntax (Toggle Plain Text)
for(j=2; j<=i/2; j++) { if((i%j) == 0) { isprime = false; } }
Its significane is known when we are programming on a large scale. I presume
0
#7 28 Days Ago
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.
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.
I give up!
1) What word becomes shorter if you add a letter to it? [ Solved by : niek_e ]
2) What does this sequence equal to : (.5u - .5a)(.5u-.5b)(.5u-.5c) ...
3) What is the 123456789 prime numer?![]() |
Similar Threads
- Giving code to posters rather than helping them (IT Professionals' Lounge)
- help understanding how this program works (C)
- Can Someone please check my project & comment/tips (C)
- Need help With this C++ Program..Confused.. (C++)
Other Threads in the C++ Forum
- Previous Thread: Unrelated function call changes variable values (apparently)
- Next Thread: Borland Strings
| Thread Tools | Search this Thread |
api array based binary bitmap c++ c/c++ calculator char char* class classes code coding compile console conversion count database delete deploy desktop developer directshow dll download dynamic dynamiccharacterarray email encryption error file forms fstream function functions game givemetehcodez google graph gui homeworkhelp iamthwee ifstream input int java lib linkedlist linker linux list loop looping loops map math matrix memory multiple news node number numbertoword output pointer problem program programming project python random read recursion recursive reference return rpg sorting string strings temperature template templates test text text-file tree unix url variable vector video visualstudio win32 windows winsock word wordfrequency wxwidgets






