Counting finite abelian groups

Question

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;jjj<length;jjj++) {               // check if divisible by small primes (for speed)
        if(i==primes[jjj]){return true;}
        else if(i%primes[jjj]==0){return false;}
    }
    for(long long jjj=i-1;jjj>1;jjj--) {            // trial division
        if(i%jjj==0){return false;}
    } 
    return true;
}  

Prime Factorization

The first function (factorizePartial) recursively populates a list with all the primes that divide it, however many times they divide it. The 0th element is the index that describes how many elements of the list are actually used. For example, 16 maps to [5,2,2,2,2,2,.....].

The second function (factorize) takes the above list and turns it into a 2-dimensional array of primes and their powers. For example, 16 maps to [ [2,2], [2,5], ....], where the 0th array is again the maximal index.

void factorizePartial(long long n, long long (*list)[99]) {  
    static int index =1;    
    if(n>1) {
        while(1) {
            assert(index<99);
            if( isPrime(n) ) {
                (*list)[index]=n;
                index++; 
                break;
            }
            else {
                for(long i=2;i<n;i++)
                {
                    if(n%i==0) {
                        factorizePartial(i,list);
                        n/=i;
                        break;
                    }
                }
            }
        }
        (*list)[0]=index;
    }
    else if(n==1) {(*list)[0]=2;(*list)[1]=1;}
    else {
        index=1;
    }
}

and

void factorize(long long n, long long (*ptr)[99][2] )
{
    long long list[99];
    factorizePartial(n, &list);
    int index=1;
    bool alreadyDone=false;
    for(int i=1;i<list[0];i++)
    {
        alreadyDone=false;
        for(int j=1;j<index;j++) {
            if(list[i]==(*ptr)[j][0]) {
                alreadyDone=true;
                break;
            }
        }
        if(!alreadyDone) {
            (*ptr)[index][0]=list[i];
            index++;
            int counter=1;
            for(int k=i+1;k<list[0];k++) {
                if(list[k]==list[i]) {
                    counter++;
                }
            }
            (*ptr)[index-1][1]=counter;
        }
    }
    (*ptr)[0][0]=index;
    (*ptr)[0][1]=index;
}

Integer Partition

The following two functions are based off the entry in the Wikipedia article on integers partitions:

long long p(long long n, long long m) {
    if (n<=1) {
        return 1;
    }
    if (m>n) {
        return p(n,n);
    }
    long long sum =0;
    for (long long k=1;k<=m;k++) {
        sum+= p(n-k,k);
    }
    return sum;
}

long long integerPartitions(long long n) {
    return p(n,n);
}

Putting it all together

As described in the challenge description, this function breaks a number down into its prime factors and their associated powers. It then takes the products of the integer partitions of the powers.

long long numberOfAbelianGroups(long long n) {
    if(n==0){return 0;}
    long long list[99][2];
    factorize(n,&list);
    long long product = 1;
    for(int k=1;k<list[0][0];k++) {
        product*=integerPartitions(list[k][1]);
    }
    return product;
}

Answer 1

• 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.

Answer 2

Since your primary interest is apparently in improving the speed of your factorizing, I'll concentrate on that for the moment.

Right now, you're starting with a small set of candidate primes for factoring. Especially for large numbers, however, these may not provide much help. One possibility would be to instead use something like the Sieve of Eratosthenes to find all the primes up to the square root of the largest number in the input. Then use those (up to the square root of each input) to factorize each input.

A quick check using a (minutely modified version of) the code I posted in another question shows that this using this technique, your largest number can be factored in about a minute.

There are certainly other approaches that are substantially more efficient still--especially a case like this, where the last number is the square of a fairly large prime. Even so, I'm reasonably certain that using this technique will improve speed sufficiently to fit in the given time limit pretty easily for the specified inputs.

As one more point: you do want to read in all the inputs, find the largest number, do the sieve once based on that largest number, then use the factors you've found as the candidates for all the inputs. This avoids re-doing the sieve for each input, which can be a fairly substantial savings overall, especially if the number of inputs might be large.