Perfect Numbers

output.txt

Factor table built in 1314 ms
6 (1 ms)
28 (1 ms)
496 (4 ms)
8128 (14 ms)
33550336 (48787 ms)

perfectNumber-threaded.cc

// Use -std=c++11 -pthread
// Runs about six times as fast as the JS version on 4 threads

#include <chrono>
#include <iostream>
#include <thread>

// The size to allocate for temporary arrays. If you're getting segfaults it's probably because this is too low.
#define TEMP_ARRAY_SIZE 1000
#define THREAD_COUNT 4
#define UINT unsigned long

class FactorTable {
    public:
        FactorTable(UINT size);
        FactorTable(UINT size, UINT *table);
        ~FactorTable();

        bool GetOwnsTable() { return ownsTable; };
        UINT *GetTable() { return table; };
        UINT GetSize() { return size; };

        UINT *GetPrimeFactors(UINT n);
        UINT *GetFactors(UINT n);
        bool IsPrime(UINT n);
        bool IsPerfect(UINT n);
    private:
        bool ownsTable;

        UINT *table;
        UINT size;

        UINT *factors;
        UINT factorsSize;

        UINT *primeFactors;
        UINT primeFactorsSize;

        UINT *uniquePrimeFactors;
        UINT *uniquePrimeFactorsCounts;
        UINT *buildFactorsIndices;
        UINT uniquePrimeFactorsSize;

        void ComputeFactors(UINT n);
        void ComputePrimeFactors(UINT n);
        void BuildFactorsList(int dim = 0);
};

FactorTable::FactorTable(UINT _size) : ownsTable(true), size(_size), factorsSize(0), primeFactorsSize(0), uniquePrimeFactorsSize(0) {
    table = new UINT[2 * size]();

    factors = new UINT[TEMP_ARRAY_SIZE];
    primeFactors = new UINT[TEMP_ARRAY_SIZE];
    uniquePrimeFactors = new UINT[TEMP_ARRAY_SIZE];
    uniquePrimeFactorsCounts = new UINT[TEMP_ARRAY_SIZE];
    buildFactorsIndices = new UINT[TEMP_ARRAY_SIZE];

    table[0] = 1;
    table[1] = 1;

    UINT i, j, m, n;

    for (n = 2; n <= size; n++) {
        i = 2 * (n - 1);

        if (table[i] == 0) {
            table[i] = n;
            table[i + 1] = 1;

            for (m = n + n; m <= size; m += n) {
                j = 2 * (m - 1);

                if (table[j] == 0) {
                    table[j] = n;
                    table[j + 1] = m / n;
                }
            }
        }
    }
}

FactorTable::FactorTable(UINT _size, UINT *_table) : ownsTable(false), size(_size), table(_table), factorsSize(0), primeFactorsSize(0), uniquePrimeFactorsSize(0) {
    factors = new UINT[TEMP_ARRAY_SIZE];
    primeFactors = new UINT[TEMP_ARRAY_SIZE];
    uniquePrimeFactors = new UINT[TEMP_ARRAY_SIZE];
    uniquePrimeFactorsCounts = new UINT[TEMP_ARRAY_SIZE];
    buildFactorsIndices = new UINT[TEMP_ARRAY_SIZE];
}

FactorTable::~FactorTable() {
    if (ownsTable) {
        delete[] table;
    }

    delete[] factors;
    delete[] primeFactors;
    delete[] uniquePrimeFactors;
    delete[] uniquePrimeFactorsCounts;
    delete[] buildFactorsIndices;
}

bool FactorTable::IsPrime(UINT n) {
    return n != 1 && table[2 * n - 1] == 1;
}

bool FactorTable::IsPerfect(UINT n) {
    ComputeFactors(n);

    int i;
    UINT sum = 0;

    for (i = 0; i < factorsSize - 1; i++) {
        sum += factors[i];
    }

    return sum == n;
}

UINT *FactorTable::GetPrimeFactors(UINT n) {
    ComputePrimeFactors(n);

    int i;
    UINT *primeFactorsList = new UINT[primeFactorsSize];

    for (i = 0; i < primeFactorsSize; i++) {
        primeFactorsList[i] = primeFactors[i];
    }

    return primeFactorsList;
}

UINT *FactorTable::GetFactors(UINT n) {
    ComputeFactors(n);

    int i;
    UINT *factorsList = new UINT[factorsSize];

    for (i = 0; i < factorsSize; i++) {
        factorsList[i] = factors[i];
    }

    return factorsList;
}

void FactorTable::ComputeFactors(UINT n) {
    if (n == 1) {
        factors[0] = 1;
        factorsSize = 1;
        return;
    }

    ComputePrimeFactors(n);

    int i, j, s;

    uniquePrimeFactorsSize = 0;

    for (i = 0; i < primeFactorsSize; i++) {
        for (j = 0; j < uniquePrimeFactorsSize; j++) {
            if (uniquePrimeFactors[j] == primeFactors[i]) {
                uniquePrimeFactorsCounts[j]++;
                goto factorFound; // yeah, yeah...
            }
        }

        uniquePrimeFactors[uniquePrimeFactorsSize] = primeFactors[i]; 
        uniquePrimeFactorsCounts[uniquePrimeFactorsSize] = 1;

        uniquePrimeFactorsSize++;

        factorFound:;
    }

    BuildFactorsList();
}

void FactorTable::ComputePrimeFactors(UINT n) {
    UINT i = 2 * (n - 1);

    primeFactors[0] = table[i];
    primeFactorsSize = 1;

    while (table[i + 1] != 1) {
        i = 2 * (table[i + 1] - 1);
        primeFactors[primeFactorsSize++] = table[i];
    }
}

void FactorTable::BuildFactorsList(int dim) {
    int i, j;

    if (dim == 0) {
        factorsSize = 0;
    }

    if (dim < uniquePrimeFactorsSize) {
        for (i = 0; i <= uniquePrimeFactorsCounts[dim]; i++) {
            buildFactorsIndices[dim] = i;
            BuildFactorsList(dim + 1);
        }
    } else {
        UINT factor = 1;

        for (i = 0; i < uniquePrimeFactorsSize; i++) {
            for (j = 0; j < buildFactorsIndices[i]; j++) {
                factor *= uniquePrimeFactors[i];
            }
        }

        factors[factorsSize++] = factor;
    }
}

int main() {
    std::chrono::steady_clock::time_point ftStart = std::chrono::steady_clock::now();
    FactorTable ft(35e6);

    std::cout << "Factor table built in " 
        << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - ftStart).count() 
        << "ms" << std::endl;

    std::chrono::steady_clock::time_point startTime = std::chrono::steady_clock::now();

    int i;
    int n = 1;
    int max = ft.GetSize();

    auto runThread = [&]() {
        FactorTable context(ft.GetSize(), ft.GetTable());
        int local;

        while (true) {
            local = n++;

            if (local > max) {
                break;
            }

            if (context.IsPerfect(local)) {
                std::cout << local << " ("
                    << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - startTime).count() 
                    << " ms)" << std::endl;
            }
        }
    };

    std::thread threads[THREAD_COUNT];

    for (i = 0; i < THREAD_COUNT; i++) {
        threads[i] = std::thread(runThread);
    }

    for (i = 0; i < THREAD_COUNT; i++) {
        threads[i].join();
    }
};

perfectNumber.cc

// Use -std=c++11
// Runs about twice as fast as the JS version

#include <chrono>
#include <iostream>

// The size to allocate for temporary arrays. If you're getting segfaults it's probably because this is too low.
#define TEMP_ARRAY_SIZE 1000
#define UINT unsigned long

class FactorTable {
    public:
        FactorTable(UINT size);
        ~FactorTable();

        UINT GetSize() { return size; };

        UINT *GetPrimeFactors(UINT n);
        UINT *GetFactors(UINT n);
        bool IsPrime(UINT n);
        bool IsPerfect(UINT n);
    private:
        UINT *table;
        UINT size;

        UINT *factors;
        UINT factorsSize;

        UINT *primeFactors;
        UINT primeFactorsSize;

        UINT *uniquePrimeFactors;
        UINT *uniquePrimeFactorsCounts;
        UINT *buildFactorsIndices;
        UINT uniquePrimeFactorsSize;

        void ComputeFactors(UINT n);
        void ComputePrimeFactors(UINT n);
        void BuildFactorsList(int dim = 0);
};

FactorTable::FactorTable(UINT _size) : size(_size), factorsSize(0), primeFactorsSize(0), uniquePrimeFactorsSize(0) {
    table = new UINT[2 * size]();

    factors = new UINT[TEMP_ARRAY_SIZE];
    primeFactors = new UINT[TEMP_ARRAY_SIZE];
    uniquePrimeFactors = new UINT[TEMP_ARRAY_SIZE];
    uniquePrimeFactorsCounts = new UINT[TEMP_ARRAY_SIZE];
    buildFactorsIndices = new UINT[TEMP_ARRAY_SIZE];

    table[0] = 1;
    table[1] = 1;

    UINT i, j, m, n;

    for (n = 2; n <= size; n++) {
        i = 2 * (n - 1);

        if (table[i] == 0) {
            table[i] = n;
            table[i + 1] = 1;

            for (m = n + n; m <= size; m += n) {
                j = 2 * (m - 1);

                if (table[j] == 0) {
                    table[j] = n;
                    table[j + 1] = m / n;
                }
            }
        }
    }
}

FactorTable::~FactorTable() {
    delete[] table;
    delete[] factors;
    delete[] primeFactors;
    delete[] uniquePrimeFactors;
    delete[] uniquePrimeFactorsCounts;
    delete[] buildFactorsIndices;
}

bool FactorTable::IsPrime(UINT n) {
    return table[2 * n - 1] == 1;
}

bool FactorTable::IsPerfect(UINT n) {
    ComputeFactors(n);

    int i;
    UINT sum = 0;

    for (i = 0; i < factorsSize - 1; i++) {
        sum += factors[i];
    }

    return sum == n;
}

UINT *FactorTable::GetPrimeFactors(UINT n) {
    ComputePrimeFactors(n);

    int i;
    UINT *primeFactorsList = new UINT[primeFactorsSize];

    for (i = 0; i < primeFactorsSize; i++) {
        primeFactorsList[i] = primeFactors[i];
    }

    return primeFactorsList;
}

UINT *FactorTable::GetFactors(UINT n) {
    ComputeFactors(n);

    int i;
    UINT *factorsList = new UINT[factorsSize];

    for (i = 0; i < factorsSize; i++) {
        factorsList[i] = factors[i];
    }

    return factorsList;
}

void FactorTable::ComputeFactors(UINT n) {
    if (n == 1) {
        factors[0] = 1;
        factorsSize = 1;
        return;
    }

    ComputePrimeFactors(n);

    int i, j, s;

    uniquePrimeFactorsSize = 0;

    for (i = 0; i < primeFactorsSize; i++) {
        for (j = 0; j < uniquePrimeFactorsSize; j++) {
            if (uniquePrimeFactors[j] == primeFactors[i]) {
                uniquePrimeFactorsCounts[j]++;
                goto factorFound; // yeah, yeah...
            }
        }

        uniquePrimeFactors[uniquePrimeFactorsSize] = primeFactors[i]; 
        uniquePrimeFactorsCounts[uniquePrimeFactorsSize] = 1;

        uniquePrimeFactorsSize++;

        factorFound:;
    }

    BuildFactorsList();
}

void FactorTable::ComputePrimeFactors(UINT n) {
    UINT i = 2 * (n - 1);

    primeFactors[0] = table[i];
    primeFactorsSize = 1;

    while (table[i + 1] != 1) {
        i = 2 * (table[i + 1] - 1);
        primeFactors[primeFactorsSize++] = table[i];
    }
}

void FactorTable::BuildFactorsList(int dim) {
    int i, j;

    if (dim == 0) {
        factorsSize = 0;
    }

    if (dim < uniquePrimeFactorsSize) {
        for (i = 0; i <= uniquePrimeFactorsCounts[dim]; i++) {
            buildFactorsIndices[dim] = i;
            BuildFactorsList(dim + 1);
        }
    } else {
        UINT factor = 1;

        for (i = 0; i < uniquePrimeFactorsSize; i++) {
            for (j = 0; j < buildFactorsIndices[i]; j++) {
                factor *= uniquePrimeFactors[i];
            }
        }

        factors[factorsSize++] = factor;
    }
}

int main() {
    std::chrono::steady_clock::time_point ftStart = std::chrono::steady_clock::now();
    FactorTable ft(35e6);

    std::cout << "Factor table built in " 
        << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - ftStart).count() 
        << "ms" << std::endl;

    std::chrono::steady_clock::time_point startTime = std::chrono::steady_clock::now();

    for (int i = 1; i <= ft.GetSize(); i++) {
        if (ft.IsPerfect(i)) {
            std::cout << i << " ("
                << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - startTime).count() 
                << " ms)" << std::endl;
        }
    }
};

perfectNumber.js

var nLoop = function (maxes, fn, dim, indices) {
    if (dim === void 0) { dim = 0; }
    if (indices === void 0) { indices = []; }
    if (dim < maxes.length) {
        var max = maxes[dim];
        for (var i = 0; i <= max; i++) {
            indices[dim] = i;
            nLoop(maxes, fn, dim + 1, indices);
        }
    }
    else {
        fn(indices);
    }
};
var FactorTable = /** @class */ (function () {
    function FactorTable(size) {
        var records = new Uint32Array(size * 2); // new Array(size);
        records[0] = 1;
        records[1] = 1;
        for (var n = 2; n <= size; n++) {
            var i = 2 * (n - 1);
            if (!records[i]) {
                records[i] = n;
                records[i + 1] = 1;
                for (var m = n + n; m <= size; m += n) {
                    var j = 2 * (m - 1);
                    if (!records[j]) {
                        records[j] = n;
                        records[j + 1] = m / n;
                    }
                }
            }
        }
        this.size = size;
        this.records = records;
    }
    FactorTable.prototype.isPrime = function (n) {
        if (n > this.size) {
            return undefined;
        }
        return this.records[2 * n - 1] === 1;
    };
    FactorTable.prototype.isPerfect = function (n) {
        if (n > this.size) {
            return undefined;
        }
        var factors = this.factors(n);
        var sum = -n;
        for (var _i = 0, factors_1 = factors; _i < factors_1.length; _i++) {
            var factor = factors_1[_i];
            sum += factor;
        }
        return sum === n;
    };
    FactorTable.prototype.factors = function (n) {
        if (n > this.size) {
            return undefined;
        }
        if (n === 1) {
            return [1];
        }
        var primeFactorsList = this.primeFactors(n);
        var uniqueFactors = [];
        var uniqueFactorsCounts = [];
        var factorsList = [];
        for (var _i = 0, primeFactorsList_1 = primeFactorsList; _i < primeFactorsList_1.length; _i++) {
            var factor = primeFactorsList_1[_i];
            var i = uniqueFactors.indexOf(factor);
            if (i === -1) {
                uniqueFactors.push(factor);
                uniqueFactorsCounts.push(1);
            }
            else {
                uniqueFactorsCounts[i]++;
            }
        }
        nLoop(uniqueFactorsCounts, function (powers) {
            var factor = 1;
            for (var i = 0; i < powers.length; i++) {
                factor *= Math.pow(uniqueFactors[i], powers[i]);
            }
            factorsList.push(factor);
        });
        return factorsList;
    };
    FactorTable.prototype.primeFactors = function (n) {
        if (n > this.size) {
            return undefined;
        }
        var records = this.records;
        var i = 2 * (n - 1);
        var list = [records[i]];
        while (records[i + 1] !== 1) {
            i = 2 * (records[i + 1] - 1);
            list.push(records[i]);
        }
        return list;
    };
    return FactorTable;
}());
var ftStart = Date.now();
var ft = new FactorTable(35e6);
console.log("Factor table built in " + (Date.now() - ftStart) + " ms");
var startTime = Date.now();
for (var n = 1; n <= ft.size; n++) {
    if (ft.isPerfect(n)) {
        console.log(n.toString(10) + " (" + (Date.now() - startTime) + " ms)");
    }
}

perfectNumber.ts

const nLoop = (maxes: number[], fn: (indices: number[]) => void, dim: number = 0, indices: number[] = []) => {
    if (dim < maxes.length) {
        const max = maxes[dim];

        for (let i = 0; i <= max; i++) {
            indices[dim] = i;
            nLoop(maxes, fn, dim + 1, indices);
        }
    } else {
        fn(indices);
    }
};

class FactorTable {
    public size: number;
    public records: Uint32Array;

    constructor(size: number) {
        const records = new Uint32Array(size * 2); // new Array(size);

        records[0] = 1;
        records[1] = 1;

        for (let n = 2; n <= size; n++) {
            const i = 2 * (n - 1);

            if (!records[i]) {
                records[i] = n;
                records[i + 1] = 1;

                for (let m = n + n; m <= size; m += n) {
                    const j = 2 * (m - 1);

                    if (!records[j]) {
                        records[j] = n;
                        records[j + 1] = m / n;
                    }
                }
            }
        }

        this.size = size;
        this.records = records;
    }

    public isPrime(n: number) {
        if (n > this.size) {
            return undefined;
        }

        return this.records[2 * n - 1] === 1;
    }

    public isPerfect(n: number) {
        if (n > this.size) {
            return undefined;
        }

        const factors = this.factors(n)!;

        let sum = -n;
        for (const factor of factors) {
            sum += factor;
        }

        return sum === n;
    }

    public factors(n: number) {
        if (n > this.size) {
            return undefined;
        }

        if (n === 1) {
            return [1];
        }

        const primeFactorsList = this.primeFactors(n)!;
        const uniqueFactors: number[] = [];
        const uniqueFactorsCounts: number[] = [];

        const factorsList: number[] = [];

        for (const factor of primeFactorsList) {
            const i = uniqueFactors.indexOf(factor);

            if (i === -1) {
                uniqueFactors.push(factor);
                uniqueFactorsCounts.push(1);
            } else {
                uniqueFactorsCounts[i]++;
            }
        }

        nLoop(uniqueFactorsCounts, powers => {
            let factor = 1;

            for (let i = 0; i < powers.length; i++) {
                factor *= uniqueFactors[i] ** powers[i];
            }

            factorsList.push(factor);
        });

        return factorsList;
    }

    public primeFactors(n: number) {
        if (n > this.size) {
            return undefined;
        }

        const records = this.records;

        let i = 2 * (n - 1);
        const list: number[] = [records[i]];

        while (records[i + 1] !== 1) {
            i = 2 * (records[i + 1] - 1);
            list.push(records[i]);
        }

        return list;
    }
}

const ftStart = Date.now();
const ft = new FactorTable(35e6);

console.log(`Factor table built in ${Date.now() - ftStart} ms`);

const startTime = Date.now();

for (let n = 1; n <= ft.size; n++) {
    if (ft.isPerfect(n)) {
        console.log(`${n.toString(10)} (${Date.now() - startTime} ms)`);
    }
}