C++ Coding Exercise - Factor Utility on Windows | Algorithms, Blockchain and Cloud

If you are a linux user, you may know this ‘useless’ command factor which will print the prime factors of given positive integers on command line. On execution, the factor will parse the command line parameters into groups of positive integers (delimiter by spaces), and try to compute the prime factors of each positive integers if applicable line by line. Why should I bother with this? In modern cryptography, the prime factorization plays a fundamental part. There are efficient algorithms to detect whether a number is a prime but there are none to de-factorize the numbers i.e. break the integers into prime factors.

factor-linux C++ Coding Exercise - Factor Utility on Windows 32 bit algorithms beginner c / c++ code code library implementation linux math programming languages windows

Now, the pre-compiled binary factor for windows platform can be downloaded [here] (g++, zipped, 169KB) cnt C++ Coding Exercise - Factor Utility on Windows 32 bit algorithms beginner c / c++ code code library implementation linux math programming languages windows . Most functionalities are preserved compared to the factor on linux platforms, apart from some small differences in the field of message output (such as usage, help).

factor-win C++ Coding Exercise - Factor Utility on Windows 32 bit algorithms beginner c / c++ code code library implementation linux math programming languages windows

The core algorithm is to use a prime from the smallest (2) and divide the original number until it is not dividable. Print the prime once it can be dividable by the original number. Skip even numbers because they are not prime unless it is two. Check primes for divisors no more than the square roots.

The core code is:

    int prime = 2;
    cout << num << ": ";
    while (num != 1) {
        while (num % prime == 0) {
            cout << prime << " ";
            num /= prime;
        }
        if (prime != 2) {
            for (;;) {
                prime += 2; // skip even numbers
                bool flag = true;
                /* test for prime */
                for (int k = 2; k < (int)sqrt(prime); k ++) {
                    if (prime % k == 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            }
        } else {
            prime = 3; // special case
            continue;
        }
    }

    int prime = 2;
    cout << num << ": ";
    while (num != 1) {
        while (num % prime == 0) {
            cout << prime << " ";
            num /= prime;
        }
        if (prime != 2) {
            for (;;) {
                prime += 2; // skip even numbers
                bool flag = true;
                /* test for prime */
                for (int k = 2; k < (int)sqrt(prime); k ++) {
                    if (prime % k == 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            }
        } else {
            prime = 3; // special case
            continue;
        }
    }

And the full complete C++ source (compiled under g++) is:

#include <iostream>
#include <math.h>
#include <string.h>
 
using namespace std;
 
typedef unsigned long long BIG;
const int UPPER_RANGE_LEN = 20;
 
void printHelp() {
    cout << "Print Prime Factors of a Positive Number" << endl;
    cout << "by http://HelloACM.com" << endl; 
} 
 
void process(char *s) 
    {     
        BIG num = 0;     
        int len = strlen(s);     
        if (len >= UPPER_RANGE_LEN) {
        cout << "factor: '" << s << "' too large or invalid" << endl;
        return;
    }
    for (int i = 0; i < len; i ++) {
        char d = s[i];
        if ((d < '0') || (d > '9')) {
            cout << "factor: '" << s << "' is not a valid positive integer" << endl;
            return ;
        }
        num = num * 10 + (int)d - 48;
    }
    if (num <= 0) {
        cout << num << ":" << endl;
        return;
    }
    int prime = 2;
    cout << num << ": ";
    while (num != 1) {
        while (num % prime == 0) {
            cout << prime << " ";
            num /= prime;
        }
        if (prime != 2) {
            for (;;) {
                prime += 2; // skip even numbers
                bool flag = true;
                /* test for prime */
                for (int k = 2; k < (int)sqrt(prime); k ++) {
                    if (prime % k == 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            }
        } else {
            prime = 3; // special case
            continue;
        }
    }
    cout << endl;
}
 
int main(int argc, char **argv) {
    if (argc == 1) {
        printHelp();
        return 1;
    } else {
        for (int i = 1; i < argc; i ++) {
            process(argv[i]);
        }
    }
    return 0;
}

#include <iostream>
#include <math.h>
#include <string.h>

using namespace std;

typedef unsigned long long BIG;
const int UPPER_RANGE_LEN = 20;

void printHelp() {
    cout << "Print Prime Factors of a Positive Number" << endl;
    cout << "by http://HelloACM.com" << endl; 
} 

void process(char *s) 
    {     
        BIG num = 0;     
        int len = strlen(s);     
        if (len >= UPPER_RANGE_LEN) {
        cout << "factor: '" << s << "' too large or invalid" << endl;
        return;
    }
    for (int i = 0; i < len; i ++) {
        char d = s[i];
        if ((d < '0') || (d > '9')) {
            cout << "factor: '" << s << "' is not a valid positive integer" << endl;
            return ;
        }
        num = num * 10 + (int)d - 48;
    }
    if (num <= 0) {
        cout << num << ":" << endl;
        return;
    }
    int prime = 2;
    cout << num << ": ";
    while (num != 1) {
        while (num % prime == 0) {
            cout << prime << " ";
            num /= prime;
        }
        if (prime != 2) {
            for (;;) {
                prime += 2; // skip even numbers
                bool flag = true;
                /* test for prime */
                for (int k = 2; k < (int)sqrt(prime); k ++) {
                    if (prime % k == 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    break;
                }
            }
        } else {
            prime = 3; // special case
            continue;
        }
    }
    cout << endl;
}

int main(int argc, char **argv) {
    if (argc == 1) {
        printHelp();
        return 1;
    } else {
        for (int i = 1; i < argc; i ++) {
            process(argv[i]);
        }
    }
    return 0;
}

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...

639 words
Last Post: Modern getch() implementation on Windows C/C++
Next Post: C/C++ Coding Exercise - Finding Approximation of Pi using Monto-Carlo Algorithm

The Permanent URL is: C++ Coding Exercise – Factor Utility on Windows

Related posts:

Leave a Reply