Help Translate this Simple? Algorithm

[gretty]

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 :P

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:

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

[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

[gretty]

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

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

[daviddoria]

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

#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

[mrnutty]

Let me try to explain further of the algorithm below :

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
}