The concept, is to add the decomposition into prime factors of a number to get its 'ancestors'.



The objective is to demonstrate that the choice of the algorithm can be crucial in term of performance.
This solution could be compared to the solution that would use the decomposition into primes for all the numbers between 1 and 333.



The problem is to list, for a delimited set of ancestors (from 1 to 99) :

- the total of their own ancestors (LEVEL),

- their own ancestors (ANCESTORS),

- the total of the direct descendants (DESCENDANTS),

- all the direct descendants.



You only have to consider the prime factors < 100.

A grand total of the descendants has to be printed at the end of the list.

The task should be accomplished in a reasonable time-frame.



Example :

46 = 2*23 --> 2+23 = 25, is the parent of 46.
25 = 5*5  --> 5+5  = 10, is the parent of 25.
10 = 2*5  --> 2+5  = 7,  is the parent of 10.
7 is a prime factor and, as such, has no parent.

46 has 3 ancestors (7, 10 and 25).
46 has 557 descendants.
The list layout and the output for Parent [46] :

[46] Level: 3
Ancestors: 7, 10, 25
Descendants: 557
129, 205, 246, 493, 518, 529, 740, 806, 888, 999, 1364, 1508, 1748, 2552, 2871, 3128, 3255, 3472, 3519, 3875, 3906, 4263, 4650, 4960, 5075, 5415, 5580, 5776, 5952, 6090, 6279, 6496, 6498, 6696, 6783, 7250, 7308, 7475, 7533, 8075, 8151, 8619, 8700, 8855, 8970, 9280, 9568, 9690, 10115, 10336, 10440, 10626, 10764, 11136, 11495, 11628, 11745, 12103, 12138, 12155, 12528, 12650, 13794, 14094, 14399, 14450, 14586, 15180, 15379, 15778, 16192, 17290, 17303, 17340, 18216, 18496, 20482, 20493, 20570, 20748, 20808, 21658, 21970, 22540, 23409, 24684, 24700, 26026, 26364, 27048, 29260, 29282, 29640, 30429, 30940, 31616, 32200, 33345, 35112, 35568, 36225, 36652, 37128, 37180, 38640, 39501, 40014, 41216, 41769, 41800, 43125, 43470, 44044, 44200, 44616, 46000, 46368, 47025, 49725, 50160, 50193, 51750, 52136, 52164, 52360, 53040, 53504, 55200, 56430, 56576, 58653, 58880, 58905, 59670, 60192, 62100, 62832, 62920, 63648, 66240, 66248, 67716, 69825, 70125, 70656, 70686, 70785, 71604, 74480, 74520, 74529, 74536, 74800, 75504, 79488, 83125, 83790, 83835, 83853, 84150, 84942, 87465, 88725, 89376, 89424, 89760, 93296, 94640, 95744, 99750, 99825, 100548, 100602, 100980, 104125, 104958, 105105, 105625, 106400, 106470, 106480, 107712, 112112, 113568, 118750, 119700, 119790, 121176, 124509, 124950, 125125, 126126, 126750, 127680, 127764, 127776, 133280, 135200, 136192, 136323, 142500, 143640, 143748, 148225, 148750, 149940, 150150, 152000, 152100, 153216, 156065, 159936, 160160, 161595, 162240, 171000, 172368, 173056, 177870, 178500, 178750, 179928, 180180, 182400, 182520, 184877, 187278, 189728, 190400, 192192, 192375, 193914, 194560, 194688, 202419, 205200, 205335, 211750, 212500, 213444, 214200, 214500, 216216, 218880, 219024, 222950, 228480, 228800, 230850, 233472, 240975, 243243, 243712, 246240, 246402, 254100, 255000, 257040, 257400, 262656, 264110, 267540, 271040, 272000, 274176, 274560, 277020, 285376, 286875, 289170, 289575, 292864, 295488, 302500, 304920, 306000, 308448, 308880, 316932, 318500, 321048, 325248, 326400, 329472, 332424, 343035, 344250, 347004, 347490, 348160, 361179, 363000, 365904, 367200, 370656, 373977, 377300, 382200, 387200, 391680, 407680, 408375, 411642, 413100, 416988, 417792, 429975, 435600, 440640, 452760, 455000, 458640, 464640, 470016, 470596, 482944, 489216, 490050, 495616, 495720, 509355, 511875, 515970, 522720, 528768, 539000, 543312, 546000, 550368, 557568, 557685, 582400, 588060, 594864, 606375, 609375, 611226, 614250, 619164, 627264, 646800, 650000, 655200, 669222, 672280, 689920, 698880, 705672, 721875, 727650, 731250, 737100, 745472, 756315, 770000, 776160, 780000, 786240, 793881, 806736, 827904, 832000, 838656, 859375, 866250, 873180, 877500, 884520, 900375, 907578, 924000, 931392, 936000, 943488, 960400, 985600, 995085, 998400, 1031250, 1039500, 1047816, 1053000, 1061424, 1064960, 1071875, 1080450, 1100000, 1108800, 1123200, 1152480, 1178793, 1182720, 1184625, 1194102, 1198080, 1229312, 1237500, 1247400, 1261568, 1263600, 1277952, 1286250, 1296540, 1320000, 1330560, 1347840, 1372000, 1382976, 1403325, 1408000, 1419264, 1421550, 1437696, 1485000, 1496880, 1516320, 1531250, 1543500, 1555848, 1584000, 1596672, 1617408, 1646400, 1670625, 1683990, 1689600, 1705860, 1750329, 1756160, 1782000, 1796256, 1802240, 1819584, 1837500, 1852200, 1900800, 1960000, 1975680, 2004750, 2020788, 2027520, 2047032, 2083725, 2107392, 2138400, 2162688, 2187500, 2205000, 2222640, 2280960, 2302911, 2352000, 2370816, 2405700, 2433024, 2480625, 2500470, 2508800, 2566080, 2625000, 2646000, 2667168, 2737152, 2800000, 2822400, 2886840, 2953125, 2976750, 3000564, 3010560, 3079296, 3125000, 3150000, 3175200, 3211264, 3247695, 3360000, 3386880, 3464208, 3515625, 3543750, 3572100, 3584000, 3612672, 3750000, 3780000, 3810240, 3897234, 4000000, 4032000, 4064256, 4218750, 4252500, 4286520, 4300800, 4500000, 4536000, 4572288, 4587520, 4800000, 4822335, 4838400, 5062500, 5103000, 5120000, 5143824, 5160960, 5400000, 5443200, 5505024, 5740875, 5760000, 5786802, 5806080, 6075000, 6123600, 6144000, 6193152, 6480000, 6531840, 6553600, 6834375, 6889050, 6912000, 6967296, 7290000, 7348320, 7372800, 7776000, 7838208, 7864320, 8201250, 8266860, 8294400, 8388608, 8748000, 8817984, 8847360, 9331200, 9437184, 9841500, 9920232, 9953280, 10497600, 10616832, 11160261, 11197440, 11809800, 11943936, 12597120, 13286025, 13436928, 14171760, 15116544, 15943230, 17006112, 19131876
Some figures :

The biggest descendant number : 3^33 = 5.559.060.566.555.523 (parent 99)

Total Descendants 546.986

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define MAXPRIME 99						// upper bound for the prime factors
#define MAXPARENT 99					// greatest parent number
#define NBRPRIMES 30					// max number of prime factors
#define NBRANCESTORS 10					// max number of parent's ancestors
 
FILE *FileOut;
char format[] = ", %lld";
 
int Primes[NBRPRIMES];					// table of the prime factors
int iPrimes;							// max index of the prime factor table
 
short Ancestors[NBRANCESTORS];			// table of the parent's ancestors
 
struct Children {
	long long Child;
	struct Children *pNext;
};
struct Children *Parents[MAXPARENT+1][2];	// table pointing to the root and to the last descendants (per parent)
int CptDescendants[MAXPARENT+1];			// counter table of the descendants (per parent)
long long MaxDescendant = (long long) pow(3.0, 33.0);	// greatest descendant number
 
short GetParent(long long child);
struct Children *AppendChild(struct Children *node, long long child);
short GetAncestors(short child);
void PrintDescendants(struct Children *node);
int GetPrimes(int primes[], int maxPrime);
 
int main()
{
	long long Child;
	short i, Parent, Level;
	int TotDesc = 0;
 
	if ((iPrimes = GetPrimes(Primes, MAXPRIME)) < 0)
		return 1;
 
	for (Child = 1; Child <= MaxDescendant; Child++)
	{
		if (Parent = GetParent(Child))
		{
			Parents[Parent][1] = AppendChild(Parents[Parent][1], Child);
			if (Parents[Parent][0] == NULL)
				Parents[Parent][0] = Parents[Parent][1];
			CptDescendants[Parent]++;
		}
	}
 
	if (MAXPARENT > MAXPRIME)
		if (GetPrimes(Primes, MAXPARENT) < 0)
			return 1;
 
	if (fopen_s(&FileOut, "Ancestors.txt", "w"))
		return 1;
 
	for (Parent = 1; Parent <= MAXPARENT; Parent++)
	{
		Level = GetAncestors(Parent);
 
		fprintf(FileOut, "[%d] Level: %d\n", Parent, Level);
 
		if (Level)
		{
			fprintf(FileOut, "Ancestors: %d", Ancestors[0]);
 
			for (i = 1; i < Level; i++)
				fprintf(FileOut, ", %d", Ancestors[i]);
		}
		else
			fprintf(FileOut, "Ancestors: None");
 
		if (CptDescendants[Parent])
		{
			fprintf(FileOut, "\nDescendants: %d\n", CptDescendants[Parent]);
			strcpy_s(format, "%lld");
			PrintDescendants(Parents[Parent][0]);
			fprintf(FileOut, "\n");
		}
		else
			fprintf(FileOut, "\nDescendants: None\n");
 
		fprintf(FileOut, "\n");
		TotDesc += CptDescendants[Parent];
	}
 
	fprintf(FileOut, "Total descendants %d\n\n", TotDesc);
	if (fclose(FileOut))
		return 1;
 
	return 0;
}
 
short GetParent(long long child)
{
	long long Child = child;
	short Parent = 0;
	short Index = 0;
 
	while (Child > 1 && Parent <= MAXPARENT)
	{
		if (Index > iPrimes)
			return 0;
 
		while (Child % Primes[Index] == 0)
		{
			Child /= Primes[Index];
			Parent += Primes[Index];
		}
 
		Index++;
	}
 
	if (Parent == child || Parent > MAXPARENT || child == 1)
		return 0;
 
	return Parent;
}
 
struct Children *AppendChild(struct Children *node, long long child)
{
	static struct Children *NodeNew;
 
	if (NodeNew = (struct Children *) malloc(sizeof(struct Children)))
	{
		NodeNew->Child = child;
		NodeNew->pNext = NULL;
		if (node != NULL)
			node->pNext = NodeNew;
	}
 
	return NodeNew;
}
 
short GetAncestors(short child)
{
	short Child = child;
	short Parent = 0;
	short Index = 0;
 
	while (Child > 1)
	{
		while (Child % Primes[Index] == 0)
		{
			Child /= Primes[Index];
			Parent += Primes[Index];
		}
 
		Index++;
	}
 
	if (Parent == child || child == 1)
		return 0;
 
	Index = GetAncestors(Parent);
 
	Ancestors[Index] = Parent;
	return ++Index;
}
 
void PrintDescendants(struct Children *node)
{
	static struct Children *NodeCurr;
	static struct Children *NodePrev;
 
	NodeCurr = node;
	NodePrev = NULL;
	while (NodeCurr)
	{
		fprintf(FileOut, format, NodeCurr->Child);
		strcpy_s(format, ", %lld");
		NodePrev = NodeCurr;
		NodeCurr = NodeCurr->pNext;
		free(NodePrev);
	}
 
	return;
}
 
int GetPrimes(int primes[], int maxPrime)
{
	if (maxPrime < 2)
		return -1;
 
	int Index = 0, Value = 1;
	int Max, i;
 
	primes[0] = 2;
 
	while ((Value += 2) <= maxPrime)
	{
		Max = (int) floor(sqrt((double) Value));
 
		for (i = 0; i <= Index; i++)
		{
			if (primes[i] > Max)
			{
				if (++Index >= NBRPRIMES)
					return -1;
 
				primes[Index] = Value;
				break;
			}
 
			if (Value % primes[i] == 0)
				break;
		}
	}
 
	return Index;
}