Second ACM practice problem.

So the Brock computer science club (CSC) released the second ACM practice problem question. Once again, it was pretty trivial to do, but the difficulty comes through implementing a solution quickly.

There were two problems. The first was to find all the prime factors of any number between 1 and 1 billion. They specifically wanted us to try this with 11741730, I’m guessing because this number has the most prime factors. The coding style is pretty bad because there was a sub-competition to create the smallest .c or .cpp file that was still a correct solution.

Code here:

///Timothy Coish, Sept. 25, 2014. ACM practice problem 2, part 1

#include <iostream>

int main()

{

int num = 11741730;

unsigned int factors[32] = {0};

bool deepBreak = false;

while(!deepBreak){

for (short i = 0; i < 32; i++){

if (deepBreak) break;

for (unsigned long long j = 2; j < num; j++){

if (num%j == 0) {

factors[i] = j;

num/=j;

if(num == 2){

factors[i+1] = 2;

deepBreak = true;

}

break;

} else if (j == num-1){

factors[i] = num;

deepBreak = true;

}

}

}

}

for (short i = 0; i < 32; i++){

if (factors[i] == 0) return 0;

std::cout << factors[i] << “, “;

}

}

For those interested, the primes are:

2, 3, 5, 7, 11, 13, 17, 23.

The second part was, for any number between 1 and 1 billion, find the number of unique prime factors. So for example 48 becomes 2*2*2*2*3, so it has 2 unique factors. 96 would also have 2 unique factors. 11741730 would have 8 unique factors. This time there was no sub-competition, so I was free to code cleanly.

Code here:

/*********************************************************************************

Part 2, Timothy Coish, Sept. 25, 2014. ACM practice problem 2.

*********************************************************************************/

#include <iostream>

int* ReturnFactors(int num, int* pSize);

int NumDiffFactors(int* pFactors, int size);

int main()

{

int num;

std::cout << “Enter num between 1-1000000000: “;

std::cin >> num;

while (num < 1 || num > 1000000000){

std::cout << “\nTry again: “;

std::cin >> num;

}

int numFactors;

int* pFactors = ReturnFactors(num, &numFactors);

std::cout << “Num Unique Factors: ” << NumDiffFactors(pFactors, numFactors);

return 0;

}

int* ReturnFactors(int num, int* pSize)

{

int factors[32] = {0};

//this just puts the factors in the array.

bool deepBreak = false;

while(!deepBreak){

for (int i = 0; i < 32; i++){

if (deepBreak) break;

for (int j = 2; j < num; j++){

if (num%j == 0) {

factors[i] = j;

num/=j;

if(num == 2){

factors[i+1] = 2;

deepBreak = true;

}

break;

} else if (j == num-1){

factors[i] = num;

deepBreak = true;

}

}

}

}

//now we need to return a smaller array with just the right factors

int realSize = 0;

for (int i = 0; i < 32; i++){

if (factors[i] == 0) {

realSize = i;

break;

}

}

int* realFactors = new int(realSize);

for (int i = 0; i < realSize; i++){

realFactors[i] = factors[i];

}

*pSize = realSize;

return realFactors;

}

//basically, add the factors to the array, unless we already have it in the array.

int NumDiffFactors(int* pFactors, int size)

{

int validPrimes = 0;

bool alreadyFound = false;

int checkArray[32] = {0};

for (int i = 0; i < size; i++){

alreadyFound = false;

for (int j = 0; j < i; j++){ //if it’s already in the array.

if (pFactors[i] == checkArray[j]){

alreadyFound = true;

}

}

if(!alreadyFound){

checkArray[validPrimes] = pFactors[i];

validPrimes++;

}

}

return validPrimes;

}

I’m aware that even this code isn’t exactly beautiful, but I was trying to impose time restraints on myself. I’m especially dissapointed with the main function and int* ReturnFactors(int num, int* pSize). Since this has the ugly side effect of initializing *pSize. It makes the code confusing to read. I could change it but it doesn’t matter that much to me. Also there’s not really that much point to making an array of exactly the right size. It’s unneccessary and makes the code harder to read, albiet also making the code feel ‘better’, whatever that means.

Incidentally I had a small bug, that I needed a debugger to catch.