Prev: C++ Quiz
Next: how to convert integer to string
From: Chris on 16 Sep 2005 14:52
I've been working out of Bruce Eckel's book, and I am trying to solve
the following problem:

Write a program that uses two nested for loops and the modulus operator
(%) to detect and print prime numbers (integral numbers that are not
evenly divisible by any other numbers except for themselves and 1).

Here is what I have written so far:

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

int main() {
cout << "Enter an integer: ";
int prime;
cin >> prime;

for (int i = 1; i <= prime; ++i) {
for (int j = 1; j <= i; ++j) {
int remainder = i % j;
cout << "Remainder for " << i << "/" << j << ": " << remainder
<< endl;
}
}

return 0;
}

Here is some output:
Enter an integer: 7
Remainder for 1/1: 0
Remainder for 2/1: 0
Remainder for 2/2: 0
Remainder for 3/1: 0
Remainder for 3/2: 1
Remainder for 3/3: 0
Remainder for 4/1: 0
Remainder for 4/2: 0
Remainder for 4/3: 1
Remainder for 4/4: 0
Remainder for 5/1: 0
Remainder for 5/2: 1
Remainder for 5/3: 2
Remainder for 5/4: 1
Remainder for 5/5: 0
Remainder for 6/1: 0
Remainder for 6/2: 0
Remainder for 6/3: 0
Remainder for 6/4: 2
Remainder for 6/5: 1
Remainder for 6/6: 0
Remainder for 7/1: 0
Remainder for 7/2: 1
Remainder for 7/3: 1
Remainder for 7/4: 3
Remainder for 7/5: 2
Remainder for 7/6: 1
Remainder for 7/7: 0

My problem is trying to figure out where to go next. How do I tell my
program to look at output like

Remainder for 7/1: 0
Remainder for 7/2: 1
Remainder for 7/3: 1
Remainder for 7/4: 3
Remainder for 7/5: 2
Remainder for 7/6: 1
Remainder for 7/7: 0

and say "Aha! Here is a prime number!"?

I'm sure the answer is staring at me straight in the face. I just
can't see it.

From: Aggro on 16 Sep 2005 15:09
Chris wrote:

> Remainder for 7/1: 0
> Remainder for 7/2: 1
> Remainder for 7/3: 1
> Remainder for 7/4: 3
> Remainder for 7/5: 2
> Remainder for 7/6: 1
> Remainder for 7/7: 0

First, adjust your loops so that you don't divide by 1 and by the number
itself. You should get following results:

// For not a prime:
Remainder for 6/2: 0 <- Result was zero, no need to check the rest
Remainder for 6/3: 0
Remainder for 6/4: 2
Remainder for 6/5: 1

// For prime number:
Remainder for 7/2: 1
Remainder for 7/3: 1
Remainder for 7/4: 3
Remainder for 7/5: 2
Remainder for 7/6: 1 <- Last result was not zero, this is a prime number

Now, how can you tell that 6 is not a prime number, but 7 is? Well
that's simple. 6 has result that is 0 (6%2 = 0). So when the result is
zero, you know that that number can't be a prime number. So you can end
your loop right after you see the zero.

To find out which numbers are prime numbers, you have to check all
numbers. If after all checks the number hasn't produced any zeros, then
it is a prime number.
From: osmium on 16 Sep 2005 15:41
"Aggro" writes:

> To find out which numbers are prime numbers, you have to check all
> numbers. If after all checks the number hasn't produced any zeros, then it
> is a prime number.

Nitpick. Check all numbers up to the square root of the number being
investigated for primality.


From: Richard Heathfield on 16 Sep 2005 16:05
osmium said:

> "Aggro" writes:
>
>> To find out which numbers are prime numbers, you have to check all
>> numbers. If after all checks the number hasn't produced any zeros, then
>> it is a prime number.
>
> Nitpick. Check all numbers up to the square root of the number being
> investigated for primality.

For extra credit: Check all *prime* numbers up to the square root of the
number being investigated for primality.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/2005
http://www.cpax.org.uk
email: rjh at above domain
From: Andrew Koenig on 18 Sep 2005 12:42
"osmium" <r124c4u102(a)comcast.net> wrote in message
news:3p0lfsF82rlpU1(a)individual.net...

>> To find out which numbers are prime numbers, you have to check all
>> numbers. If after all checks the number hasn't produced any zeros, then
>> it is a prime number.

> Nitpick. Check all numbers up to the square root of the number being
> investigated for primality.

Additional nitpick. Computing the square root is not guaranteed to be
exact, even when an exact result exists. So, for example, there is no
guarantee that sqrt(25.0) == 5. [There is such a guarantee on
implementations that follow the IEEE floating-point standard, but not all
implementations do so, even if they claim to do so.]

Therefore, if you use floating-point arithmetic to compute the square root,
and use that square root as an upper bound for a primality-testing loop, you
might get into rounding trouble. Worse: Such errors are intrinsically
untestable, because they might appear only on implementations that you do
not have available for testing.

If the preceding description does not make it clear to you how to avoid the
problem, I suggest that you avoid floating-point arithmetic when it is part
of an integer-oriented computation such as prime testing.


 | 
Pages: 1
Prev: C++ Quiz
Next: how to convert integer to string