Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* ---------------------------------------------------------------------------
- In this .cpp file you will provide the source code for function definitions
- specified in Primes.h, along with any "helper" functions you wish to
- implement.
- Student Name: Sarah Oloumi
- Student Number: 100991673
- References:
- 1) Hinek,J."Lectures Notes for COMP1406B- Introduction to Computer Science II" [PDF documents].Retrieved from cuLearn: https://www.carleton.ca/cuLearn/ (Winter2016)
- 2) "Prime Factorization Calculator." CalculatorSoup Online Calculator Resource. Web. 07 Feb. 2016. <http://www.calculatorsoup.com/calculators/math/prime-factors.php>.
- 3) Wikipedia. Wikimedia Foundation. Web. 07 Feb. 2016. <https://en.wikipedia.org/wiki/Prime-factor_FFT_algorithm>.
- 4) Spraul, V. Anton. Think like a Programmer: An Introduction to Creative Problem Solving. Print. Chapters Three and Four
- 5) "Prime Factorization of a Number." YouTube. YouTube. Web. 07 Feb. 2016. <https://www.youtube.com/watch?v=6PDtgHhpCHo>.
- 6) "Std::setw." Setw. Web. 08 Feb. 2016. <http://www.cplusplus.com/reference/iomanip/setw/>.
- 7) "Std::setfill." Setfill. Web. 08 Feb. 2016. <http://www.cplusplus.com/reference/iomanip/setfill/?kw=setfill>.
- ---------------------------------------------------------------------------
- */
- // Problem 2
- /*
- For the primeFactors function, we want to create an algorithm that calculates and gives us the prime factors
- of a given number in an array(myArray) which we will initialize at the very beginning of the function.
- */
- #include "Primes.h"
- using namespace std;
- int* primeFactors(int n)
- {
- // create array in heap
- int* myArray = new int [n];
- // variable that keeps track of how full the array is:
- int myLength = 0 ;
- // prime number can only be divided by 1 or by itself.. and it cant be
- // divided any further so check if n == 1
- if (n == 1)
- {
- // std::cout<<1;
- return (0);
- }
- int constant = 2;
- // Here we want to create a while loop where while the given number is
- // greater than or equal to 4.
- while (constant*constant <= n)
- { // So now we want to create an if statement where it will check to
- // see if the module of the given number is exactly 0
- // so there are no remainders.
- if ( n%constant == 0)
- { // Now, what we want to do is to make it so
- // every number that is found and is prime
- // will be thrown in to myArray
- myArray[myLength] = constant;
- myLength++ ;
- //std::cout<<y<<" ";
- n/= constant;
- }
- // If there is a remainder then the following will be executed:
- else
- {
- constant++;
- }
- }
- // once we get out of the while loop, that means the numbers are prime
- if(n>1)
- {
- // every number that is found and is prime will be thrown in to myArray
- myArray[myLength] = n;
- myLength++ ;
- //std::cout<<n<<" " << std::endl;
- }
- // BUBBLE SORT!
- // create a variable that holds on to the numbers that are being checked
- int hold = 0 ;
- // Nested for loops are created so that we can iterate through the factors, find out if
- // a number is greater than another, and then put it at the beginning of the array so the
- // order is from greatest to least.
- for (int i = 0 ; i < myLength - 1 ; i++)
- {
- for (int s=0 ; s < myLength - i - 1; s++)
- {
- if (myArray[s] < myArray[s+1])
- {
- hold = myArray[s];
- myArray[s] = myArray[s+1];
- // assign whatever hold is holding on to, to myArray
- myArray[s+1] = hold;
- }
- }
- }
- // At the end of each array, the number one needed to be added... so this that
- myArray[myLength] = 1;
- myLength++ ;
- // this here was used to test out my code so I could see
- //if it was printing out the right things or not
- for (int u = 0; u<myLength; u ++)
- { //prints my array of prime factors
- std::cout<<myArray[u]<< " ";
- }
- std::cout<< "" << std::endl;
- return myArray;
- }
- /*
- The second function in ex 2 is implemented here.
- The point of this function is to return an array of integer arrays,
- so basically they're double pointers. The array is going to have the prime
- factorizations of the numbers from 2 to the number given to us in the argument (n).
- */
- int** allPrimeFactors(int n)
- { // create an array of integers in heap
- int** myArray = new int*[n];
- // for each position call the array we made before
- int x = 0;
- for(x = 2; x<=n; x++)
- { // Assigning the function primeFactors to our array
- // We also say x-2 so the index starts at 0
- myArray[x] = primeFactors(x-2);
- }
- return myArray;
- }
- /*
- So the function here takes array of integer arrays as input + and the length of the array.
- It will then output a stringstream that has a string representation of the factorization array.
- */
- std::string displayPrimeFactors(int** factorization, int length)
- {
- // create a variable that will return the output. Its the string representation of the factorization array.
- stringstream output;
- // Sets the field width to be used on output operations.
- // in this case we set it = to x since we dont know
- int x = 0;
- setw(x);
- for (int i=2; i < length+1; i++)
- {
- // This takes care of the left side:
- output<<setw(x);
- // Sets the fill character to the value of parameter c as if a call to stream member fill(c).
- // The fill character is used in output insertion operations to fill the spaces with padding results to the field width
- // You must include <iomanip> to use this manipulator.
- output << setfill('0');
- output << "=";
- for(int k=0; k < length; k++)
- {
- output << std::setw(x) << std::setfill('0') << x << " = ";
- int length = 0;
- while(factorization[k][length] != 1 )
- {
- length ++;
- break;
- }
- for(int j=length-1; j>=0; j--)
- {
- cout << factorization[k][length];
- }
- }
- /*
- for(int k=0; k<length; k++)
- {
- // if our number is not 0/1 then :
- // if(allPrimeFactors(length+1)[i-2][k]!= 0 || allPrimeFactors(length-2)[i-2][k]!= 1 )
- {
- output<< "i";
- }
- // if nor then break( so if its 0 or 1 then break)
- else
- {
- break;
- }
- output << allPrimeFactors(length +1)[i-2][k];
- }*/
- std::cout << output <<"\n ,"<< std::endl;
- }
- return output.str();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement