How to resolve the algorithm Primes - allocate descendants to their ancestors step by step in the zkl programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Primes - allocate descendants to their ancestors step by step in the zkl programming language

Table of Contents

Problem Statement

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 : The list layout and the output for Parent [46] : Some figures :

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Primes - allocate descendants to their ancestors step by step in the zkl programming language

Source code in the zkl programming language

const maxsum=99;
 
primes:=Utils.Generator(Import("sieve.zkl").postponed_sieve)
        .pump(List,'wrap(p){ (p<=maxsum) and p or Void.Stop });

descendants,ancestors:=List()*(maxsum + 1), List()*(maxsum + 1);

foreach p in (primes){
   descendants[p].insert(0,p);
   foreach s in ([1..descendants.len() - p - 1]){
      descendants[s + p].merge(descendants[s].apply('*(p)));
   }
}

    // descendants[prime] is a list that starts with prime, remove prime. 4: ???
foreach p in (primes + 4) { descendants[p].pop(0) }
 
ta,td:=0,0;
foreach s in ([1..maxsum]){
   foreach d in (descendants[s].filter('<=(maxsum))){
      ancestors[d]=ancestors[s].copy() + s;
   }

   println("%2d Ancestors: ".fmt(s),ancestors[s].len() and ancestors[s] or "None");
   println("   Descendants: ", if(z:=descendants[s]) 
				String(z.len()," : ",z) else "None");
   ta+=ancestors[s].len(); td+=descendants[s].len();
} 
println("Total ancestors: %,d".fmt(ta));
println("Total descendants: %,d".fmt(td));

  

You may also check:How to resolve the algorithm Terminal control/Cursor positioning step by step in the Z80 Assembly programming language
You may also check:How to resolve the algorithm Special characters step by step in the Julia programming language
You may also check:How to resolve the algorithm Strip comments from a string step by step in the PL/I programming language
You may also check:How to resolve the algorithm Terminal control/Dimensions step by step in the Applesoft BASIC programming language
You may also check:How to resolve the algorithm Day of the week step by step in the PL/M programming language