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

#Warn
#SingleInstance force
#NoEnv            ; Recommended for performance and compatibility with future AutoHotkey releases.
SendMode Input    ; Recommended for new scripts due to its superior speed and reliability.
SetBatchLines, -1
SetFormat, IntegerFast, D
 
MaxPrime    = 99		; upper bound for the prime factors
MaxAncestor = 99		; greatest parent number
 
Descendants := []
 
Primes := GetPrimes(MaxPrime)
Exclusions := Primes.Clone()
Exclusions.Insert(4)
 
if A_Is64bitOS
{
	Loop, % MaxAncestor
		Descendants.Insert({})
 
	for i, Prime in Primes
	{
		Descendants[Prime, Prime] := 0
 
		for Parent, Children in Descendants
		{
			if ((Sum := Parent+Prime) > MaxAncestor)
				break
 
			for pr in Children
				Descendants[Sum, pr*Prime] := 0
		}
	}
 
	for i, v in Exclusions
		Descendants[v].Remove(v, "")
}
else
{
	Loop, % MaxAncestor
		Descendants.Insert([])
 
	for i, Prime in Primes
	{
		Descendants[Prime].Insert(Prime)
 
		for Parent, Children in Descendants
		{
			if ((Sum := Parent+Prime) > MaxAncestor)
				break
 
			for j, pr in Children
				Descendants[Sum].Insert(pr*Prime)
		}
	}
 
	for i, v in Exclusions
		Descendants[v].Remove()
}
 
if (MaxAncestor > MaxPrime)
	Primes := GetPrimes(MaxAncestor)
 
IfExist, %A_ScriptName%.txt
	FileDelete, %A_ScriptName%.txt
 
;-------------------------------------------------------
; Arrays :
; Integer keys are stored using the native integer type
; 32bit key max = 2.147.483.647
; 64bit key max = 9.223.372.036.854.775.807
;-------------------------------------------------------
Tot_desc = 0
for Parent, Children in Descendants
{
	ls_desc =
	if A_Is64bitOS
	{
		nb_desc = 0
		for pr in Children
			ls_desc .= ", " pr, nb_desc++
		ls_desc := LTrim(ls_desc, ", ")
	}
	else
	{
		nb_desc := Children.MaxIndex()
		for i, pr in Children
			ls_desc .= "," pr
		ls_desc := LTrim(ls_desc, ",")
 
		Sort, ls_desc, N D`,
		StringReplace, ls_desc, ls_desc, `,,`,%A_Space%, All
	}
 
	ls_anc =
	nb_anc := GetAncestors(ls_anc, Parent)
	ls_anc := LTrim(ls_anc, ", ")
 
	FileAppend, % "[" Parent "] Level: " nb_anc "`r`nAncestors: " (nb_anc ? ls_anc : "None") "`r`n"
				 , %A_ScriptName%.txt
 
	if nb_desc
	{
		Tot_desc += nb_desc
		FileAppend, % "Descendants: " nb_desc "`r`n" ls_desc "`r`n`r`n", %A_ScriptName%.txt
	}
	else
		FileAppend, % "Descendants: None`r`n`r`n", %A_ScriptName%.txt
}
 
FileAppend, % "Total descendants " Tot_desc, %A_ScriptName%.txt
return
 
GetAncestors(ByRef _lsAnc, _child)
{
	global Primes
 
	lChild := _child
	lIndex := lParent := 0
 
	while lChild > 1
	{
		lPrime := Primes[++lIndex]
		while !mod(lChild, lPrime)
			lChild //= lPrime, lParent += lPrime
	}
 
	if (lParent = _child or _child = 1)
		return 0
 
	_lsAnc := ", " lParent _lsAnc
	li := GetAncestors(_lsAnc, lParent)
	return ++li
}
 
GetPrimes(_maxPrime=0, _nbrPrime=0)
{
	lPrimes := []
 
	if (_maxPrime >= 2 or _nbrPrime >= 1)
	{
		lPrimes.Insert(2)
		lValue = 1
 
		while (lValue += 2) <= _maxPrime or lPrimes.MaxIndex() < _nbrPrime
		{
			lMaxPrime := Floor(Sqrt(lValue))
 
			for lKey, lPrime in lPrimes
			{
				if (lPrime > lMaxPrime)		; if prime divisor is greater than Floor(Sqrt(lValue))
				{
					lPrimes.Insert(lValue)
					break
				}
 
				if !Mod(lValue, lPrime)
					break
			}
		}
	}
 
	return lPrimes
}