Prime Factors

Discussion in 'C++' started by Freyr, Feb 28, 2006.

  1. Freyr

    Freyr Guest

    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
     
    Freyr, Feb 28, 2006
    #1
    1. Advertising

  2. 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
    > 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
    --
    Please remove capital As from my address when replying by mail
     
    Victor Bazarov, Feb 28, 2006
    #2
    1. Advertising

  3. * 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
    > new number" is asking.


    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?
     
    Alf P. Steinbach, Feb 28, 2006
    #3
  4. Freyr

    Jerry Coffin Guest

    In article <1141149975.533951.14730
    @t39g2000cwt.googlegroups.com>, says...
    > 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.


    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.

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Feb 28, 2006
    #4
  5. Freyr

    Freyr Guest

    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:

    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?)
     
    Freyr, Feb 28, 2006
    #5
  6. 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
    --
    Please remove capital As from my address when replying by mail
     
    Victor Bazarov, Feb 28, 2006
    #6
  7. Freyr

    Freyr Guest

    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
     
    Freyr, Feb 28, 2006
    #7
  8. Freyr

    Jerry Coffin Guest

    In article <1141161602.183121.294530
    @j33g2000cwa.googlegroups.com>, says...
    > 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...

    --
    Later,
    Jerry.

    The universe is a figment of its own imagination.
     
    Jerry Coffin, Feb 28, 2006
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    2
    Views:
    1,351
    Stefan Ram
    Jul 29, 2006
  2. zak

    Top Ten SEO Factors

    zak, Feb 19, 2007, in forum: Java
    Replies:
    1
    Views:
    475
    Andrew Thompson
    Feb 19, 2007
  3. srinivas.hyd
    Replies:
    0
    Views:
    575
    srinivas.hyd
    Oct 26, 2007
  4. Chris Gordon-Smith
    Replies:
    2
    Views:
    260
    Miles Bader
    Sep 12, 2011
  5. Jeremy Fischer
    Replies:
    0
    Views:
    212
    Jeremy Fischer
    Jan 16, 2005
Loading...

Share This Page