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

Imports System.Math
 
Module Module1
    Const MAXPRIME = 99                             ' upper bound for the prime factors
    Const MAXPARENT = 99                            ' greatest parent number
 
    Const NBRCHILDREN = 547100                      ' max number of children (total descendants)
 
    Public Primes As New Collection()               ' table of the prime factors
    Public PrimesR As New Collection()              ' table of the prime factors in reversed order
    Public Ancestors As New Collection()            ' table of the parent's ancestors
 
    Public Parents(MAXPARENT + 1) As Integer        ' index table of the root descendant (per parent)
    Public CptDescendants(MAXPARENT + 1) As Integer ' counter table of the descendants (per parent)
    Public Children(NBRCHILDREN) As ChildStruct     ' table of the whole descendants
    Public iChildren As Integer                     ' max index of the Children table
 
    Public Delimiter As String = ", "
    Public Structure ChildStruct
        Public Child As Long
        Public pLower As Integer
        Public pHigher As Integer
    End Structure
    Sub Main()
        Dim Parent As Short
        Dim Sum As Short
        Dim i As Short
        Dim TotDesc As Integer = 0
        Dim MidPrime As Integer
 
        If GetPrimes(Primes, MAXPRIME) = vbFalse Then
            Return
        End If
 
        For i = Primes.Count To 1 Step -1
            PrimesR.Add(Primes.Item(i))
        Next
 
        MidPrime = PrimesR.Item(1) / 2
 
        For Each Prime In PrimesR
            Parents(Prime) = InsertChild(Parents(Prime), Prime)
            CptDescendants(Prime) += 1
 
            If Prime > MidPrime Then
                Continue For
            End If
 
            For Parent = 1 To MAXPARENT
                Sum = Parent + Prime
 
                If Sum > MAXPARENT Then
                    Exit For
                End If
 
                If Parents(Parent) Then
                    InsertPreorder(Parents(Parent), Sum, Prime)
                    CptDescendants(Sum) += CptDescendants(Parent)
                End If
            Next
        Next
 
        RemoveFalseChildren()
 
        If MAXPARENT > MAXPRIME Then
            If GetPrimes(Primes, MAXPARENT) = vbFalse Then
                Return
            End If
        End If
 
        FileOpen(1, "Ancestors.txt", OpenMode.Output)
 
        For Parent = 1 To MAXPARENT
            GetAncestors(Parent)
            PrintLine(1, "[" & Parent.ToString & "] Level: " & Ancestors.Count.ToString)
 
            If Ancestors.Count Then
                Print(1, "Ancestors: " & Ancestors.Item(1).ToString)
                For i = 2 To Ancestors.Count
                    Print(1, ", " & Ancestors.Item(i).ToString)
                Next
                PrintLine(1)
                Ancestors.Clear()
            Else
                PrintLine(1, "Ancestors: None")
            End If
 
            If CptDescendants(Parent) Then
                PrintLine(1, "Descendants: " & CptDescendants(Parent).ToString)
                Delimiter = ""
                PrintDescendants(Parents(Parent))
                PrintLine(1)
                TotDesc += CptDescendants(Parent)
            Else
                PrintLine(1, "Descendants: None")
            End If
 
            PrintLine(1)
        Next
        Primes.Clear()
        PrimesR.Clear()
        PrintLine(1, "Total descendants " & TotDesc.ToString)
        PrintLine(1)
        FileClose(1)
    End Sub
    Function InsertPreorder(_index As Integer, _sum As Short, _prime As Short)
        Parents(_sum) = InsertChild(Parents(_sum), Children(_index).Child * _prime)
 
        If Children(_index).pLower Then
            InsertPreorder(Children(_index).pLower, _sum, _prime)
        End If
 
        If Children(_index).pHigher Then
            InsertPreorder(Children(_index).pHigher, _sum, _prime)
        End If
 
        Return Nothing
    End Function
    Function InsertChild(_index As Integer, _child As Long) As Integer
        If _index Then
            If _child <= Children(_index).Child Then
                Children(_index).pLower = InsertChild(Children(_index).pLower, _child)
            Else
                Children(_index).pHigher = InsertChild(Children(_index).pHigher, _child)
            End If
        Else
            iChildren += 1
            _index = iChildren
            Children(_index).Child = _child
            Children(_index).pLower = 0
            Children(_index).pHigher = 0
        End If
 
        Return _index
    End Function
    Function RemoveFalseChildren()
        Dim Exclusions As New Collection
 
        Exclusions.Add(4)
        For Each Prime In Primes
            Exclusions.Add(Prime)
        Next
 
        For Each ex In Exclusions
            Parents(ex) = Children(Parents(ex)).pHigher
            CptDescendants(ex) -= 1
        Next
 
        Exclusions.Clear()
        Return Nothing
    End Function
    Function GetAncestors(_child As Short)
        Dim Child As Short = _child
        Dim Parent As Short = 0
 
        For Each Prime In Primes
            If Child = 1 Then
                Exit For
            End If
            While Child Mod Prime = 0
                Child /= Prime
                Parent += Prime
            End While
        Next
 
        If Parent = _child Or _child = 1 Then
            Return Nothing
        End If
 
        GetAncestors(Parent)
        Ancestors.Add(Parent)
        Return Nothing
    End Function
    Function PrintDescendants(_index As Integer)
        If Children(_index).pLower Then
            PrintDescendants(Children(_index).pLower)
        End If
 
        Print(1, Delimiter.ToString & Children(_index).Child.ToString)
        Delimiter = ", "
 
        If Children(_index).pHigher Then
            PrintDescendants(Children(_index).pHigher)
        End If
 
        Return Nothing
    End Function
    Function GetPrimes(ByRef _primes As Object, Optional _maxPrime As Integer = 2) As Boolean
        Dim Value As Integer = 3
        Dim Max As Integer
        Dim Prime As Integer
 
        If _maxPrime < 2 Then
            Return vbFalse
        End If
 
        _primes.Add(2)
 
        While Value <= _maxPrime
            Max = Floor(Sqrt(Value))
 
            For Each Prime In _primes
                If Prime > Max Then
                    _primes.Add(Value)
                    Exit For
                End If
 
                If Value Mod Prime = 0 Then
                    Exit For
                End If
            Next
 
            Value += 2
        End While
 
        Return vbTrue
    End Function
End Module