Counting finite abelian groups

I wrote this code for this code golfing challenge on the CGPP sister site. It wouldn't really be a competitive entry because I had to write all the functions from scratch. (I didn't even golf anything in my code.)

I'm looking for ways to improve performance all-around.

Please see the above golfing challenge for a detailed description of the challenge, but here is a short explanation:


Given an integer, my program breaks it into unique prime factors and their powers. Then it takes each of the powers and takes the product of their integer partitions.

Here are the test cases given in the challenge:

Input Output
0 0
1 1
2 1
3 1
4 2
5 1
6 1
7 1
8 3
9 2
10 1
11 1
12 2
13 1
14 1
15 1
16 5
17 1
18 2
19 1
20 2
4611686018427387904 1300156
5587736968198167552 155232
9223371994482243049 2


The code runs in seconds for all but the last case, which takes an ungodly amount of time (more than 20 minutes on my computer). The reason for this (I believe) is that the final number, 9223371994482243049, has extremely large prime divisors and my program takes forever to prime factorize it.

Primality Checker

This function is by far the slowest part of the code. This is the largest time suck in my program. If a number has very large prime factors, this codes is very slow because it basically is trial division.

`bool isPrime(long long i) {
int primes[]={2,3,5,7,11,13,17,19,23,29}; // cheat sheet of small primes
int length = 10;
if (i==1 || i==0){return false;} // check for 1 or 0
for(int jjj=0;jjj1;jjj--) { // trial divisio

-
Primality checker is indeed suboptimal. What's worse, it computes important information (a divisor found) and discards it. I recommend to change it to

long long minimal_divisor(long long n);

and use in factorizePartial along the lines of

while (n > 1) {
        long long div = minimal_divisor(n);
        ....
        n /= div;
    }

-
Partitioning is also a time consuming procedure. Memoization is highly recommended.

StackExchange Code Review Q#107582, answer score: 2