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;
}