DaniWeb Forum Index > Software Development > C++

Help Translate this Simple? Algorithm

Please support our C++ advertiser: Intel Parallel Studio Home

•

Join Date: Apr 2009

Posts: 149

Reputation: gretty is an unknown quantity at this point

Solved Threads: 7

gretty

Offline

Junior Poster

Help Translate this Simple? Algorithm

Nov 5th, 2009

Hello

HELP

Ok I have an assignment due in 5 days. I have done everything except for one function. This function finds the smallests factors of a positive int & it multiplicities, Have I lost you yet, dont worry because I've been lost for a week now with this function

Heres the funny part... we are given the algorithm!! But I cannot for the life of me understand it. I have rewritten, written, pulled my hair out for days trying to get this function to work.

I cannot seem to get this function to work. Can you take a look at my short function below & see where my algorithm is wrong?

Algorithm we have been supplied with:

•

An outline of the above algorithm would look something like:

// positive integer I is given
P = 1
while (I > 1)
{
P = P + 1
if I mod P != 0 go back to previous statement
// now P is the smallest prime factor of I
display P
mult = 1
exactly divide I by P as often as is possible,
assigning to I the result of each exact division,
and incrementing mult with each exact division
display mult, end line
}

An example of what the function is meant to do, if you are confused like me:

•

- We input a large integer: 25852
- The function void factor will find the factors and multiplicities
- So the answer is... 2*2*23*281 = 25852

Please enter a big integer I: 25852
The number entered was 25852.
The prime factors of I are:
2 with multiplicity 2
23 with multiplicity 1
281 with multiplicity 1
Press any key to continue . . .

- As you can see (2*2)+(23*1)+(281*1) = 25852

My code which doesn't work:

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
void factor(int I) {
 
    int P = 1;
    int mult;
 
    while (I > 1) {
 
          P = P+1;
          I = I/P;
 
          while (I%P != 0) {
                 P = P+1;
                 I = I/P;
          }
 
          cout << P << " with multiplicity ";
 
          mult = 1;
 
          while (I%P == 0) {
                 I = I/P;
                 mult++;
          }
 
          cout << mult << endl;
    }
 
}
void factor(int I) {
    
    int P = 1;
    int mult;
    
    while (I > 1) {
          
          P = P+1;
          I = I/P;
          
          while (I%P != 0) {
                 P = P+1;
                 I = I/P;
          }
          
          cout << P << " with multiplicity ";
                 
          mult = 1;
          
          while (I%P == 0) {
                 I = I/P;
                 mult++;
          }
          
          cout << mult << endl;
    }
	
}

This is one of the functions I have written, if you want to see others that I have written to try to get this algorithm to work then I post them but I dont want this post any longer right now

Last edited by gretty; Nov 5th, 2009 at 7:59 pm.

•

Join Date: Feb 2008

Posts: 638

Reputation: daviddoria is a jewel in the rough

Solved Threads: 46

daviddoria daviddoria is offline

Offline

Practically a Master Poster

Nov 5th, 2009

You need to give us more of a feeling that you have really tried. Did your code produce errors? Or incorrect results? Why don't you try some simple cases like the number '4'. You should expect to see factors of 2 and 2, right? Small examples like these will help you debug the code, then you can try large numbers.

Dave

•

Join Date: Apr 2009

Posts: 149

Reputation: gretty is an unknown quantity at this point

Solved Threads: 7

gretty

Offline

Junior Poster

Nov 5th, 2009

•

Originally Posted by daviddoria

You need to give us more of a feeling that you have really tried. Did your code produce errors? Or incorrect results? Why don't you try some simple cases like the number '4'. You should expect to see factors of 2 and 2, right? Small examples like these will help you debug the code, then you can try large numbers.

Dave

Hey listen I appreciate you looking at my post but dot say I need to prove to you I have tried, I explained that I have been racking my brain for days with numurous different functions & many many wasted hours.

•

Why don't you try some simple cases like the number '4'.

OFCOURSE I have tried my function, simple & hard input alike, I wouldn't have spent days rewritting testing, rewritting without testing!?

This is what my code produces for input:
- 25852

•

2 with multiplicity 2
3 with multiplicity 2
5 with multiplicity 2
7 with multiplicity .... crash

- 8

•

2 with multiplicity 3 = works

- 135

•

6 with multiplicity ... crash

•

You need to give us more of a feeling that you have really tried.

A little bit of evidence...

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
void factorise(bigInt I) {
 
     bigInt one(1); // used to increment big ints
     bigInt zero;   // find if a bigInt equals zero
     bigInt result;
     bigInt temp(I);
     bigInt P(1);
     bigInt R(1);
     bigInt mult;
 
     while (!I.lessOrEqual(one)) {  
 
           P = P.add(one); 
           temp = I;
 
           temp.divide(P,temp,R);
 
           if (!R.isEqual(zero)) { // MAY NEED TO CHANGE TO IF STATEMENT
               temp.divide(P,temp,R); 
               P = P.add(one);
           }
 
           // Now P is the smallest prime factors of I
           P.writeBigInt();  // OR I.writeBigInt();
           cout << " with multiplicity ";
 
           mult = one;
 
           I.divide(P,temp,R);
 
           //while (R.isEqual(zero)) {
             while (!I.lessOrEqual(P)) { // && !R.isEqual(zero)) {
                  I.divide(P,I,R);
                  mult = mult.add(one);    
           }
 
           mult.writeBigInt();
           cout << endl;
 
     }
 
}
 
void fact(bigInt I) {
 
     bigInt one(1); // used to increment big ints
     bigInt zero;   // find if a bigInt equals zero
     bigInt result;
     bigInt temp(I);
     bigInt P(1);
     bigInt R(1);
     bigInt mult(1);
 
     while (!I.lessOrEqual(one)) {
           temp = I;
         while (one.lessThan(temp)) {
 
 
                temp.divide(P,temp,R);
                P = P.add(one);
                if (R.isEqual(zero) && one.lessThan(temp)) {
                    break;
                }     
          }
 
          P.writeBigInt();  // OR I.writeBigInt();
           cout << " with multiplicity ";
 
          mult = one;
 
          while (!I.lessOrEqual(P) && !R.isEqual(zero)) {
                I.divide(P,I,R);
                mult = mult.add(one);
          }
 
          mult.writeBigInt();
           cout << endl;
     }
}
 
void factor(int I) {
 
    int P = 1;
    int mult;
 
    while (I > 1) {
 
          P = P+1;
          I = I/P;
 
          while (I%P != 0) {
                 P = P+1;
                 I = I/P;
          }
 
          cout << P << " with multiplicity ";
 
          mult = 1;
 
          while (I%P == 0) {
                 I = I/P;
                 mult++;
          }
 
          cout << mult << endl;
    }
 
}
void factorise(bigInt I) {

     bigInt one(1); // used to increment big ints
     bigInt zero;   // find if a bigInt equals zero
     bigInt result;
     bigInt temp(I);
     bigInt P(1);
     bigInt R(1);
     bigInt mult;
     
     while (!I.lessOrEqual(one)) {  
            
           P = P.add(one); 
           temp = I;
           
           temp.divide(P,temp,R);
           
           if (!R.isEqual(zero)) { // MAY NEED TO CHANGE TO IF STATEMENT
               temp.divide(P,temp,R); 
               P = P.add(one);
           }
  
           // Now P is the smallest prime factors of I
           P.writeBigInt();  // OR I.writeBigInt();
           cout << " with multiplicity ";
           
           mult = one;
           
           I.divide(P,temp,R);
           
           //while (R.isEqual(zero)) {
             while (!I.lessOrEqual(P)) { // && !R.isEqual(zero)) {
                  I.divide(P,I,R);
                  mult = mult.add(one);    
           }
           
           mult.writeBigInt();
           cout << endl;
           
     }

}

void fact(bigInt I) {
     
     bigInt one(1); // used to increment big ints
     bigInt zero;   // find if a bigInt equals zero
     bigInt result;
     bigInt temp(I);
     bigInt P(1);
     bigInt R(1);
     bigInt mult(1);
     
     while (!I.lessOrEqual(one)) {
           temp = I;
         while (one.lessThan(temp)) {
           
            
                temp.divide(P,temp,R);
                P = P.add(one);
                if (R.isEqual(zero) && one.lessThan(temp)) {
                    break;
                }     
          }
          
          P.writeBigInt();  // OR I.writeBigInt();
           cout << " with multiplicity ";
          
          mult = one;
     
          while (!I.lessOrEqual(P) && !R.isEqual(zero)) {
                I.divide(P,I,R);
                mult = mult.add(one);
          }
          
          mult.writeBigInt();
           cout << endl;
     }
}

void factor(int I) {
    
    int P = 1;
    int mult;
    
    while (I > 1) {
          
          P = P+1;
          I = I/P;
          
          while (I%P != 0) {
                 P = P+1;
                 I = I/P;
          }
          
          cout << P << " with multiplicity ";
                 
          mult = 1;
          
          while (I%P == 0) {
                 I = I/P;
                 mult++;
          }
          
          cout << mult << endl;
    }
	
}

•

Join Date: Feb 2008

Posts: 638

Reputation: daviddoria is a jewel in the rough

Solved Threads: 46

daviddoria daviddoria is offline

Offline

Practically a Master Poster

Nov 5th, 2009

From that algorithm you gave I don't understand how you are supposed to get more than one factor?

Maybe this will be a good starting point for you - it just gets the smallest factor (besides 1) and multiplies it by successive integers until it gets to the "right" number (where P * mult = I).

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
#include <iostream>
 
int main()
{
  //an example input
  int I = 40;
 
  //find the smallest P that divides I evenly
  int P = 2;
 
  while(I % P != 0)
  {
    P++;
  }
 
  //output the smallest P that was found
  std::cout << P << std::endl;
 
  //show what P multiplied by everything up until the correct amount
  int mult = 1;
  while(mult * P <= I)
  {
    std::cout << mult << " * " << P << " = " << mult*P <<std::endl;
    mult++;
  }
 
  return 0;
}
#include <iostream>

int main()
{
  //an example input
  int I = 40;
  
  //find the smallest P that divides I evenly
  int P = 2;

  while(I % P != 0)
  {
    P++;
  }

  //output the smallest P that was found
  std::cout << P << std::endl;

  //show what P multiplied by everything up until the correct amount
  int mult = 1;
  while(mult * P <= I)
  {
    std::cout << mult << " * " << P << " = " << mult*P <<std::endl;
    mult++;
  }

  return 0;
}

Good luck.
Dave

•

Join Date: Dec 2008

Posts: 1,408

Reputation: firstPerson is just really nice

Solved Threads: 181

firstPerson firstPerson is offline

Offline

Nearly a Posting Virtuoso

Nov 6th, 2009

Let me try to explain further of the algorithm below :

 Help with Code Tags 
 C++ Syntax (Toggle Plain Text) 
An outline of the above algorithm would look something like:
 
// positive integer I is given
P = 1 //determines when a even factor of I is found
while (I > 1) //I is you input number
{
P = P + 1// p is now 2
if I mod P != 0 go back to previous statement //if I mod p == 1 then increment P until a factor is found
 
// now P is the smallest prime factor of I //now you found a factor for I
display P //show the factor 
mult = 1 
exactly divide I by P as often as is possible, //keep diving I by the even factor until you get a decimal division
assigning to I the result of each exact division, //now you need to find another factor of that number, so start repeating from the start
 
and incrementing mult with each exact division
display mult, end line
}
An outline of the above algorithm would look something like:

// positive integer I is given
P = 1 //determines when a even factor of I is found
while (I > 1) //I is you input number
{
P = P + 1// p is now 2
if I mod P != 0 go back to previous statement //if I mod p == 1 then increment P until a factor is found

// now P is the smallest prime factor of I //now you found a factor for I
display P //show the factor 
mult = 1 
exactly divide I by P as often as is possible, //keep diving I by the even factor until you get a decimal division
assigning to I the result of each exact division, //now you need to find another factor of that number, so start repeating from the start

and incrementing mult with each exact division
display mult, end line
}

Help with Code Tags

(Toggle Plain Text)

1) What word becomes shorter if you add a letter to it? 
      [ Solved by : niek_e, Paul Thompson, SgtMe, murtan, xavier666, jonsca]
2) What does this sequence  equal to :  (.5u - .5a)(.5u-.5b)(.5u-.5c) ...
      [*solved by : murtan, xavier666]
3) What is the 123456789th prime numer?