Velocity Reviews > C++ > Prime Factors

# Prime Factors

Freyr
Guest
Posts: n/a

 02-28-2006
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

--

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

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++;
}
}

}

to post this, she doesn't know C++.

Thanks alot
-Freyr

Victor Bazarov
Guest
Posts: n/a

 02-28-2006
Freyr wrote:
> 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

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
>
> 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++;
> }
> }
>
> }
>
> to post this, she doesn't know C++.

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

V
--

Alf P. Steinbach
Guest
Posts: n/a

 02-28-2006
* 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
>
> --
>
> I don't know exactly what "divide the number by the counter to get a

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'.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

Jerry Coffin
Guest
Posts: n/a

 02-28-2006
In article <1141149975.533951.14730
> 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

Ignore programming for the moment, and think about how
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.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Freyr
Guest
Posts: n/a

 02-28-2006
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 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
Guest
Posts: n/a

 02-28-2006
Freyr wrote:
> 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
Guest
Posts: n/a

 02-28-2006
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
Guest
Posts: n/a

 02-28-2006
In article <1141161602.183121.294530
> 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
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...

--
Later,
Jerry.

The universe is a figment of its own imagination.