Prime Factors

[Freyr]

Hello,
I'm taking an independant course in C++, and one of my questions asks
to use the following algorithm to deturmine the factors of any given
number:
--

Initialize a counter at 2
So Long as long as the counter is less than or equal to the number
if the counter divides the number evenly
display the counter
divide the number by the counter to get a new number
else
add one to the counter

--

I don't know exactly what "divide the number by the counter to get a
new number" is asking.

This is the code I have so far, I know it's incomplete and not close,
but I am completly lost.

/* 4-31 Exercise 12 - A program to display prime factors */

#include <iostream>
using namespace std;

main() {
int Number;

cout << "Enter Starting Number: ";
cin >> Number;

cout << "Prime Factors: "

for(int n=2; n <= Number {
if(Number%n == 0){
cout << n;

}
else {
n++;
}
}

}

If you're wondering about school/project cheating, my teacher asked me
to post this, she doesn't know C++.

Thanks alot
-Freyr

 

[Victor Bazarov]

I'm taking an independant course in C++, and one of my questions asks
to use the following algorithm to deturmine the factors of any given
number:

Actually you can safely stop at counter equal to square root of the
number plus one.

if the counter divides the number evenly
display the counter
divide the number by the counter to get a new number
else
add one to the counter

--

I don't know exactly what "divide the number by the counter to get a
new number" is asking.

This is the code I have so far, I know it's incomplete and not close,
but I am completly lost.

/* 4-31 Exercise 12 - A program to display prime factors */

#include <iostream>
using namespace std;

main() {

int main() {

int Number;

Useful to initialise it to something...

int Number = 42;

cout << "Enter Starting Number: ";
cin >> Number;

Beware that if you don't enter any digits, the conversion will fail and
'Number' will remain at whatever you initialised it with. It may be
useful to check its contents here and notify the user if the value is
invalid.

cout << "Prime Factors: "

for(int n=2; n <= Number {

So, 'n' is your "counter". OK.

if(Number%n == 0){
cout << n;

Good so far.

Here you are supposed to "Divide 'Number' by 'n' to get the new 'Number'".
How do you divide? How do you make "new" 'Number' to continue with that
value? Think assignment. Or compound assignment.

}
else {
n++;
}
}

}

If you're wondering about school/project cheating, my teacher asked me
to post this, she doesn't know C++.

To verify that claim it might be useful to have your teacher's e-mail
address...

V

 

[Alf P. Steinbach]

* Freyr:

I'm taking an independant course in C++, and one of my questions asks
to use the following algorithm to deturmine the factors of any given
number:
--

Initialize a counter at 2
So Long as long as the counter is less than or equal to the number
if the counter divides the number evenly
display the counter
divide the number by the counter to get a new number
else
add one to the counter

That means:

Replace the number with <the number divided by the counter>.

and the reason it's there is so as to remove this prime factor from the
number so it won't be listed again (if the same value occurs umpteen
times as prime factor, it will be listed exactly umpteen times).

This is the code I have so far, I know it's incomplete and not close,
but I am completly lost.

/* 4-31 Exercise 12 - A program to display prime factors */

#include <iostream>
using namespace std;

main() {

'main' must have result type 'int'.

 

[Jerry Coffin]

Hello,
I'm taking an independant course in C++, and one of my questions asks
to use the following algorithm to deturmine the factors of any given
number:
--

Initialize a counter at 2
So Long as long as the counter is less than or equal to the number
if the counter divides the number evenly
display the counter
divide the number by the counter to get a new number
else
add one to the counter

Ignore programming for the moment, and think about how
you'd do this in your head. Assume, for example, that the
original number is 60. You start by seeing whether that
divides by 2. It does so you print out 2. You divide 60
by 2 to get 30. You check whether 30 divides by 2, and it
does as well. You print out 2 again, then divide 30 by 2
to get 15. You check whether 15 divides by 2, and it
doesn't. You increment your counter to 3 and start over
from the top -- 15 divides by 3, so you print out three,
and then divide 15 by 3 to get 5. 5 doesn't divide by
three, so you increment your counter to 4. 5 doesn't
divide by 4 so you increment your counter to 5. 5 divides
by 5 so you print out 5. You're now done.

 

[Freyr]

That's exactly what I needed to know, I just wasn't understanding the
wording, thanks!

So it'd be:

for(int n=2; n <= Number {
if(Number%n == 0){
cout << n;
Number = Number/n;
}
else {
n++;
}

or am I missing something else? (I don't have a compiler here, I'll
have to test it tomorrow)

Victor - Knock yourself out: (e-mail address removed)

Alf - Yeah, thanks for pointing that out, I usually check my syntax
after I get the general layout done, but I missed that (How stupid of
me, eh?)

 

[Victor Bazarov]

That's exactly what I needed to know, I just wasn't understanding the
wording, thanks!

So it'd be:

for(int n=2; n <= Number {
if(Number%n == 0){
cout << n;
Number = Number/n;

A "compound assignment operator" can be used. Look it up.

}
else {
n++;
}

or am I missing something else? (I don't have a compiler here, I'll
have to test it tomorrow)

The only thing I'd add would be some kind of separator between your
outputs, like

cout << n << ' ';

otherwise your numbers are going to be printed frozen together.

V

 

[Freyr]

True enough.

I'll give compound assignment operators a look into, I'm learning all
this on my own, so it's not like I'm going out of the confined
operations to do something.

Thanks alot.
-Freyr

 

[Jerry Coffin]

That's exactly what I needed to know, I just wasn't understanding the
wording, thanks!

You're certainly welcome.

So it'd be:

for(int n=2; n <= Number {
if(Number%n == 0){
cout << n;
Number = Number/n;
}
else {
n++;
}

This looks fairly reasonable. Victor's already pointed
out the use of a compound assignment, so I won't belabor
that point.

You might also want to consider using div() to compute
the quotient and remainder/modulus together. It's not
guaranteed to improve anything, but it might. Usually if
you compute one, you get the other thrown in for free,
and div allows you to use both from a single computation
instead of doing the computation twice. Then again, a
good optimizer may already take care of that...