How to resolve the algorithm Primes - allocate descendants to their ancestors step by step in the Nim 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 Nim 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 Nim programming language
Source code in the nim programming language
import algorithm, strformat, strutils, sugar
const MaxSum = 99
func getPrimes(max: Positive): seq[int] =
if max < 2: return
result.add 2
for n in countup(3, max, 2):
block check:
for p in result:
if n mod p == 0:
break check
result.add n
let primes = getPrimes(MaxSum)
var descendants, ancestors = newSeq[seq[int]](MaxSum + 1)
for p in primes:
descendants[p].add p
for s in 1..(descendants.high - p):
descendants[s + p].add collect(newSeq, for pr in descendants[s]: p * pr)
for p in primes & 4:
discard descendants[p].pop()
var total = 0
for s in 1..MaxSum:
descendants[s].sort()
for d in descendants[s]:
if d > MaxSum: break
ancestors[d] = ancestors[s] & s
let dlength = descendants[s].len
echo &"[{s}] Level: {ancestors[s].len}"
echo "Ancestors: ", if ancestors[s].len != 0: ancestors[s].join(" ") else: "None"
echo "Descendants: ", if dlength != 0: $dlength else: "None"
if dlength != 0: echo descendants[s].join(", ")
echo ""
inc total, dlength
echo "Total descendants: ", total
You may also check:How to resolve the algorithm Sorting algorithms/Heapsort step by step in the ActionScript programming language
You may also check:How to resolve the algorithm Strip control codes and extended characters from a string step by step in the AutoHotkey programming language
You may also check:How to resolve the algorithm Halt and catch fire step by step in the Fermat programming language
You may also check:How to resolve the algorithm Sort an array of composite structures step by step in the Seed7 programming language
You may also check:How to resolve the algorithm Jacobi symbol step by step in the ALGOL W programming language