# Anyone can explain how this program works?

• (2 Pages)
• 1
• 2

## 26 Replies - 1730 Views - Last Post: 13 April 2011 - 09:39 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=227032&amp;s=3890e367140cbc4d6cd6dbb6da75f3a9&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #16 mist4lyf

Reputation: 0
• Posts: 18
• Joined: 07-April 11

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 05:22 AM

well if i put those values in, Then it would if(2%2)==0, prime=false. but that equals 0. However 2 is a prime number.

Well I already understood how the FOR works pretty much on my second post. I did go through it the same way i did a few posts ago today.

### #17 janotte

• code > sword

Reputation: 990
• Posts: 5,141
• Joined: 28-September 06

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 05:27 AM

If a=2 and b=2 then is b<a true?
Re-read how the for() loop conditional works.

### #18 mist4lyf

Reputation: 0
• Posts: 18
• Joined: 07-April 11

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 05:35 AM

Ok well for if(3%2==0)=1 instead, then prime would be true. The break then would jump to the next statement. It goes to the if(prime) then 3 would be displayed

### #19 janotte

• code > sword

Reputation: 990
• Posts: 5,141
• Joined: 28-September 06

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 05:38 AM

Well 3 is prime.
I am not sure what you are saying.

### #20 mist4lyf

Reputation: 0
• Posts: 18
• Joined: 07-April 11

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 05:42 AM

well it wasn't really a question, I was just wondering if I were right. However you didn't understand me.

If (3%2==0)
prime=false
break;
Since 3%2 is 1 instead of 0 then prime=false doesnt apply. The break; in the next line will cause a jump to the
if(prime)
cout<<"Prime: "<<a<<endl;

the prime in that brackets means prime=true?

### #21 janotte

• code > sword

Reputation: 990
• Posts: 5,141
• Joined: 28-September 06

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 05:46 AM

No.
If the if() test resolves to false then everything inside the braces "{" and "}" defining the scope of the if() test is skipped.
So the break will never be actioned in the example you give.

### #22 muballitmitte

• D.I.C Regular

Reputation: 174
• Posts: 470
• Joined: 05-November 08

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 05:49 AM

janotte,

I think he was wandering if

```if (prime)
{
//...
}

```

is the same as
```if (prime == true)
{
//...
}

```

which is true. And since he initialises prime before the "for" to true, for his test case "prime" will be printed since the break statement never gets executed.

This post has been edited by muballitmitte: 13 April 2011 - 05:49 AM

### #23 mist4lyf

Reputation: 0
• Posts: 18
• Joined: 07-April 11

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 05:53 AM

well if
If (3%2==0)resolves to false, it will go to
if(prime) next right?

Actually never got to saying thank you for your help so far. Thanks

muballitmitte, yes I was trying to know if if(prime) is the same as if(prime==true)!

### #24 mist4lyf

Reputation: 0
• Posts: 18
• Joined: 07-April 11

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 06:01 AM

Also is there a way to add up all the primes displayed and display it with a cout

### #25 r.stiltskin

• D.I.C Lover

Reputation: 1833
• Posts: 4,927
• Joined: 27-December 05

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 07:09 AM

Of course there is, and that's your assignment. It's a trivial modification of the program and if you understand how the program works you should have no trouble doing it.

And if you can't do that, then as janotte suggested earlier, you should be going back to the fundamentals of how to write a simple program -- for example, how to write a program loop that sums the numbers from 1 to 5 and prints the result.

### #26 mist4lyf

Reputation: 0
• Posts: 18
• Joined: 07-April 11

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 07:12 AM

hmm maybe I should do some sort of counter that everytime prime==true I should add one. Alright ill think about it.

### #27 NickDMax

Reputation: 2254
• Posts: 9,245
• Joined: 18-February 07

## Re: Anyone can explain how this program works?

Posted 13 April 2011 - 09:39 AM

So you have the assignment of finding the sum of all prime numbers up to a certain upper bound?

You have chosen to work from what I like to call the "naive algorithm" for finding primes. This is a very inefficient bruit force method based upon the direct definition of a prime number "A prime number's only divisors are 1 and itself" so we test each number between 2 and N-1 to see if it is a divisor.

To do this we need to loop between 2 and our test number - 1:

```for(int n = 2; n < testNumber; n++) {
if (testNumber % n == 0) {
// If we get here then the number IS NOT prime
break; // no need to check any more because we know the number is not prime!
}
}
```

Since we will want to use the knowledge outside of the loop we can fall back on the old standby of using a flag variable:

```bool isPrime = true; //assume it is true since we are testing for false hood
for(int n = 2; n < testNumber; n++) {
if (testNumber % n == 0) {
// If we get here then the number IS NOT prime
break; // no need to check any more because we know the number is not prime!
}
}
//now we can use our flag to do something with the knowledge
if (isPrime) {
cout << testNumber << " is a prime number" << endl;
} else {
cout << testNumber << " is NOT prime" << endl;
}
```

So now we can test all numbers up to the test number by adding an outer loop and you get your original function.

to add up all the primes all you need is an accumulator variable (some integer initialized to zero) and accumulator += testNumber when it is shown to be a prime.

So there are some many improvements that can be made here. for example we know that with the exception of 2 only odd number are prime so there is no need to check all of the even numbers past 2. Next we know that divisors come it pairs: given the number N if it is divisible by x then there exits a number N/x such that x * N/x == N

So all divisors are broken up into two sets, those above sqrt(N) and those below sqrt(N) and for every divisor below sqrt(N) there exists one above, and visa versa. SO! there is no need to check all numbers less than our testNumber, we only need to check up to the square root of our test number.

Finally if a number if going to be divisible by a number that number is either prime or composite, if it is composite then it is divisible by some prime number -- SO, we really only need to check divisibility by other prime numbers! So if we check for divisors that are prime numbers below sqrt(testNumber) then we can REALLY cut the amount of time needed to test a number.

These idea end up culminating in the classic "Sieve of Eratosthenes".

Take things slow and make sure you understand the intent as well as the step-by-step logic. Using the naive is fine so ensure you think about what it is trying to accomplish.