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

COMMENT cim --memory-pool-size=512 allocate-descendants-to-their-ancestors.sim ;
BEGIN
 
 
    COMMENT ABSTRACT FRAMEWORK CLASSES ;
 
    CLASS ITEM;
    BEGIN
    END ITEM;
 
    CLASS ITEMLIST;
    BEGIN
 
        CLASS ITEMARRAY(N); INTEGER N;
        BEGIN REF(ITEM) ARRAY DATA(0:N-1);
        END ITEMARRAY;
 
        PROCEDURE EXPAND(N); INTEGER N;
        BEGIN
            INTEGER I;
            REF(ITEMARRAY) TEMP;
            TEMP :- NEW ITEMARRAY(N);
            FOR I := 0 STEP 1 UNTIL SIZE-1 DO
                TEMP.DATA(I) :- ITEMS.DATA(I);
            ITEMS :- TEMP;
        END EXPAND;
 
        PROCEDURE APPEND(RI); REF(ITEM) RI;
        BEGIN
            IF SIZE + 1 > CAPACITY THEN
            BEGIN
                CAPACITY := 2 * CAPACITY;
                EXPAND(CAPACITY);
            END;
            ITEMS.DATA(SIZE) :- RI;
            SIZE := SIZE + 1;
        END APPEND;
 
        PROCEDURE APPENDALL(IL); REF(ITEMLIST) IL;
        BEGIN
            INTEGER I;
            FOR I := 0 STEP 1 UNTIL IL.SIZE-1 DO
                APPEND(IL.ELEMENT(I));
        END APPENDALL;
 
        REF(ITEM) PROCEDURE ELEMENT(I); INTEGER I;
        BEGIN
            IF I < 0 OR I > SIZE-1 THEN ERROR("ELEMENT: INDEX OUT OF BOUNDS");
            ELEMENT :- ITEMS.DATA(I);
        END ELEMENT;
 
        REF(ITEM) PROCEDURE SETELEMENT(I, IT); INTEGER I; REF(ITEM) IT;
        BEGIN
            IF I < 0 OR I > SIZE-1 THEN ERROR("SETELEMENT: INDEX OUT OF BOUNDS");
            ITEMS.DATA(I) :- IT;
        END SETELEMENT;
 
        REF(ITEM) PROCEDURE POP;
        BEGIN
            REF(ITEM) RESULT;
            IF SIZE=0 THEN ERROR("POP: EMPTY ITEMLIST");
            RESULT :- ITEMS.DATA(SIZE-1);
            ITEMS.DATA(SIZE-1) :- NONE;
            SIZE := SIZE-1;
            POP :- RESULT;
        END POP;
 
        PROCEDURE SORT(COMPARE_PROC);
            PROCEDURE COMPARE_PROC IS
                INTEGER PROCEDURE COMPARE_PROC(IT1,IT2); REF(ITEM) IT1,IT2;;
        BEGIN
            PROCEDURE SWAP(I,J); INTEGER I,J;
            BEGIN
               REF(ITEM) T;
               T :- ITEMS.DATA(I);
               ITEMS.DATA(I) :- ITEMS.DATA(J);
               ITEMS.DATA(J) :- T;
            END SWAP;
            PROCEDURE QUICKSORT(L,R); INTEGER L,R;
            BEGIN
               REF(ITEM) PIVOT;
               INTEGER I, J;
               PIVOT :- ITEMS.DATA((L+R)//2); I := L; J := R;
               WHILE I <= J DO
               BEGIN
                  WHILE COMPARE_PROC(ITEMS.DATA(I), PIVOT) < 0 DO I := I+1;
                  WHILE COMPARE_PROC(PIVOT, ITEMS.DATA(J)) < 0 DO J := J-1;
                  IF I <= J THEN
                  BEGIN SWAP(I,J); I := I+1; J := J-1;
                  END;
               END;
               IF L < J THEN QUICKSORT(L, J);
               IF I < R THEN QUICKSORT(I, R);
            END QUICKSORT;
            IF SIZE >= 2 THEN
               QUICKSORT(0,SIZE-1);
        END SORT;
 
        INTEGER CAPACITY;
        INTEGER SIZE;
        REF(ITEMARRAY) ITEMS;
 
        CAPACITY := 20;
        SIZE := 0;
        EXPAND(CAPACITY);
    END ITEMLIST;
 
 
    COMMENT PROBLEM SPECIFIC PART ;
 
 
    ITEM CLASS REALITEM(X); LONG REAL X;
    BEGIN
    END REALITEM;
 
    ITEMLIST CLASS LIST_OF_REAL;
    BEGIN
        LONG REAL PROCEDURE ELEMENT(I); INTEGER I;
            ELEMENT := ITEMS.DATA(I) QUA REALITEM.X;
 
        PROCEDURE APPEND(X); LONG REAL X;
            THIS ITEMLIST.APPEND(NEW REALITEM(X));
 
        PROCEDURE SORT;
        BEGIN
            INTEGER PROCEDURE CMP(IT1,IT2); REF(ITEM) IT1,IT2;
                CMP := IF IT1 QUA REALITEM.X < IT2 QUA REALITEM.X THEN -1 ELSE
                       IF IT1 QUA REALITEM.X > IT2 QUA REALITEM.X THEN +1 ELSE 0;
            THIS ITEMLIST.SORT(CMP);
        END SORT;
 
        PROCEDURE OUTLIST;
        BEGIN
            INTEGER I;
            TEXT FMT;
            OUTTEXT("[");
            FMT :- BLANKS(20);
            FOR I := 0 STEP 1 UNTIL SIZE-1 DO
            BEGIN
                IF I < 3 OR I > SIZE-1-3 THEN BEGIN
                    IF I > 0 THEN OUTTEXT(", ");
                    FMT.PUTFIX(ELEMENT(I), 0);
                    FMT.SETPOS(1);
                    WHILE FMT.MORE DO
                    BEGIN
                        CHARACTER C;
                        C := FMT.GETCHAR;
                        IF C <> ' ' THEN OUTCHAR(C);
                    END
                END ELSE BEGIN OUTTEXT(", ..."); I := SIZE-1-3; END;
            END;
            OUTTEXT("]");
        END OUTLIST;
    END LIST_OF_REAL;
 
 
    ITEM CLASS REALLISTITEM(LRL); REF(LIST_OF_REAL) LRL;
    BEGIN
    END REALLISTITEM;
 
    ITEMLIST CLASS LIST_OF_REALLIST;
    BEGIN
        REF(LIST_OF_REAL) PROCEDURE ELEMENT(I); INTEGER I;
            ELEMENT :- ITEMS.DATA(I) QUA REALLISTITEM.LRL;
 
        PROCEDURE APPEND(LRL); REF(LIST_OF_REAL) LRL;
            THIS ITEMLIST.APPEND(NEW REALLISTITEM(LRL));
 
        PROCEDURE OUTLIST;
        BEGIN
            INTEGER I;
            OUTTEXT("[");
            FOR I := 0 STEP 1 UNTIL SIZE-1 DO
            BEGIN
                IF I > 0 THEN OUTTEXT(", ");
                ELEMENT(I).OUTLIST;
            END;
            OUTTEXT("]");
        END OUTLIST;
    END LIST_OF_REALLIST;
 
    REF(LIST_OF_REAL) PROCEDURE GET_PRIMES(MAX);
        INTEGER MAX;
    BEGIN
        REF(LIST_OF_REAL) LPRIMES;
        LPRIMES :- NEW LIST_OF_REAL;
        IF MAX < 2 THEN
            GOTO RETURN
        ELSE
        BEGIN
            INTEGER X;
            LPRIMES.APPEND(2);
            FOR X := 3 STEP 2 UNTIL MAX DO BEGIN
                INTEGER I;
                LONG REAL P;
                FOR I := 0 STEP 1 UNTIL LPRIMES.SIZE-1 DO BEGIN
                    P := LPRIMES.ELEMENT(I);
                    IF (X / P) = ENTIER(X / P) THEN GOTO BREAK;
                END;
                LPRIMES.APPEND(X);
            BREAK:
            END;
        END;
    RETURN:
        GET_PRIMES :- LPRIMES;
    END GET_PRIMES;
 
    INTEGER MAXSUM, I, S, PRI, TOTAL, DI;
    REF(LIST_OF_REALLIST) DESCENDANTS, ANCESTORS;
    REF(LIST_OF_REAL) PRIMES, LR, LRS;
    LONG REAL P, D, PR;
    BOOLEAN TAKEWHILE;
    MAXSUM := 99;
 
    DESCENDANTS :- NEW LIST_OF_REALLIST;
    ANCESTORS   :- NEW LIST_OF_REALLIST;
    FOR I := 0 STEP 1 UNTIL MAXSUM DO BEGIN
        DESCENDANTS.APPEND(NEW LIST_OF_REAL);
        ANCESTORS  .APPEND(NEW LIST_OF_REAL);
    END;
 
    PRIMES :- GET_PRIMES(MAXSUM);
 
    FOR I := 0 STEP 1 UNTIL PRIMES.SIZE-1 DO
    BEGIN
        P := PRIMES.ELEMENT(I);
        DESCENDANTS.ELEMENT(P).APPEND(P);
        FOR S := 1 STEP 1 UNTIL DESCENDANTS.SIZE-P-1 DO
        BEGIN
            LRS :- DESCENDANTS.ELEMENT(S);
            FOR PRI := 0 STEP 1 UNTIL LRS.SIZE-1 DO
            BEGIN
                PR := LRS.ELEMENT(PRI);
                DESCENDANTS.ELEMENT(S + P).APPEND(P * PR);
            END;
        END;
    END;
 
    FOR I := 0 STEP 1 UNTIL PRIMES.SIZE-1 DO
    BEGIN
        P := PRIMES.ELEMENT(I);
        DESCENDANTS.ELEMENT(P).POP;
    END;
    DESCENDANTS.ELEMENT(4).POP;
 
    TOTAL := 0;
    FOR S := 1 STEP 1 UNTIL MAXSUM DO
    BEGIN
        LRS :- DESCENDANTS.ELEMENT(S);
        LRS.SORT;
        FOR DI := 0 STEP 1 UNTIL LRS.SIZE-1 DO
        BEGIN
            D := LRS.ELEMENT(DI);
            IF D <= MAXSUM THEN
            BEGIN
                REF(LIST_OF_REAL) ANCD;
                ANCD :- NEW LIST_OF_REAL;
                ANCD.APPENDALL(ANCESTORS.ELEMENT(S));
                ANCD.APPEND(S);
                ANCESTORS.SETELEMENT(D, NEW REALLISTITEM(ANCD));
            END
            ELSE GOTO BREAK;
        END;
        BREAK:
 
        OUTTEXT("[");
        OUTINT(S, 0);
        OUTTEXT("] LEVEL: ");
        OUTINT(ANCESTORS.ELEMENT(S).SIZE, 0);
        OUTIMAGE;
 
        OUTTEXT("ANCESTORS: ");
        ANCESTORS.ELEMENT(S).OUTLIST;
        OUTIMAGE;
 
        OUTTEXT("DESCENDANTS: ");
        OUTINT(LRS.SIZE,0);
        OUTIMAGE;
 
        LRS.OUTLIST;
        OUTIMAGE;
 
        OUTIMAGE;
        TOTAL := TOTAL + LRS.SIZE;
    END;
 
    OUTTEXT("TOTAL DESCENDANTS ");
    OUTINT(TOTAL, 0);
    OUTIMAGE;
END.