Primes - allocate descendants to their ancestors
The concept, rather simple, 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 5 and 3^33.
And to demonstrate that the choice of some options can also be dramatic (i.e. the Visual Basic .NET collection).
The problem is to list, for a delimited set of ancestors (from 5 to 99) :
- the total of their own ancestors (LEVEL),
- their own ancestors (ANCESTORS),
- the total of their descendants (DESCENDANTS),
- all their descendants.
You only have to consider the prime factors < 100.
A grand total of the decendants 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 number and, as such, has no parent. 46 has 3 ancestors (7, 10 and 25). 46 has 557 descendants.
The list layout :
[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,...
Some figures :
The biggest number : 3^33 = 5.559.060.566.555.523 (parent 99) |-----------------------------------------| |Total Descendants | 546.986 | |-----------------------------------------| |Duration in Seconds* | | | | | |AutoHotkey | 109 | |C | 4 | |Visual Basic with tables | 19 | |Visual Basic with 1 collection | 585 | |-----------------------------------------| |Size of the list in KB | 5.709 | ------------------------------------------- *On a Pentium IV.
AutoHotkey
<lang AutoHotkey>#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
start := A_Now
MaxPrime = 99 ; greatest prime number MaxAncestor = 99 ; greatest ancestor number Descendants := {}
Primes := GetPrimes(MaxPrime)
GetDescendants(1, 0, 1) ; GetDescendants(level, sum, product)
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, array in Descendants { if (Parent < 5) continue
Ancestors := GetAncestors(Parent)
ls_anc = for k, v in Ancestors ls_anc .= (A_Index = 1 ? "" : ",") v
FileAppend, % "[" Parent "] LEVEL: " (Ancestors.MaxIndex() ? Ancestors.MaxIndex() : 0) "`r`n" . "ANCESTORS: " (Ancestors.MaxIndex() ? ls_anc : "None") "`r`n" , %A_ScriptName%.txt
nb_desc = 0 ls_desc = if A_Is64bitOS for k in array ls_desc .= (A_Index = 1 ? "" : ",") k, nb_desc++ else { nb_desc := array.MaxIndex() for i, v in array ls_desc .= (i = 1 ? "" : ",") v
Sort, ls_desc, N U D`,
if ErrorLevel MsgBox, % "Number " Parent " has " ErrorLevel " duplicates" }
tot_desc += nb_desc FileAppend, % "DESCENDANTS: " nb_desc "`r`n" ls_desc "`r`n`r`n", %A_ScriptName%.txt }
FileAppend, % "Total descendants " tot_desc, %A_ScriptName%.txt
Elapsed := A_Now EnvSub, Elapsed, %Start%, seconds MsgBox % "Total descendants " tot_desc "`nElapsed time " Elapsed " seconds" return
GetDescendants(_level, _sum, _product) { global MaxAncestor, Primes, Descendants
if (_level < Primes.MaxIndex()) GetDescendants(_level+1, _sum, _product)
lPrime := Primes[_level] while (_sum += lPrime) <= MaxAncestor { _product *= lPrime
if (_sum > lPrime) { if A_Is64bitOS Descendants[_sum, _product] := true else { if !Descendants.HasKey(_sum) Descendants[_sum] := [_product] else Descendants[_sum].Insert(_product) } }
if (_level < Primes.MaxIndex()) GetDescendants(_level+1, _sum, _product) } }
GetAncestors(_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 []
lArray := GetAncestors(lParent)
lArray.Insert(lParent) return lArray }
GetPrimes(_maxPrime=0, _nbrPrime=0) { lArray := []
if (_maxPrime >= 2 or _nbrPrime > 0) { lArray.Insert(2) lValue = 3
while lValue <= _maxPrime or lArray.MaxIndex() < _nbrPrime { lMax := Floor(Sqrt(lValue))
for lKey, lPrime in lArray { if (lPrime > lMax) ; if prime divisor is greater than Floor(Sqrt(lValue)) { lArray.Insert(lValue) break }
if !Mod(lValue, lPrime) break }
lValue += 2 } }
return lArray }</lang>
C
<lang c>#include <math.h>
- include <stdio.h>
- include <time.h>
- include <stdlib.h>
- include <string.h>
- define MAXPRIME 99 // greatest prime number
- define MAXPARENT 99 // greatest parent number
- define NBRPRIMES 30 // number of primes
- define NBRANCESTORS 10 // number of parent's ancestors
FILE *FileOut; char format[] = ",%lld";
int Primes[NBRPRIMES+1]; // table of the prime numbers
struct Children { long long Child; struct Children *pLeft; struct Children *pRight; }; struct Children *Parents[MAXPARENT+1]; // table pointing to the root descendant (per parent)
int CptDescendants[MAXPARENT+1]; // counter table of the number of descendants (per parent) short Ancestors[NBRANCESTORS]; // table of the parent's ancestors
void GetChildren(short Level, short Sum, long long Product); struct Children *InsertChild(struct Children *node, long long Child); short GetAncestors(short Parent); void PrintDescendants(struct Children *node); int GetPrimes(int Primes[], int MaxPrime, int NbrPrimes);
int main() { short Parent; short Level; int i, totDesc = 0;
if (!GetPrimes(Primes, MAXPRIME, 0)) return 1;
GetChildren(0, 0, 1);
if (MAXPARENT > MAXPRIME) if (!GetPrimes(Primes, MAXPARENT, 0)) return 1;
if (fopen_s(&FileOut, "Ancestors.txt", "w")) return 1;
for (Parent = 5; Parent <= MAXPARENT; Parent++) { Level = GetAncestors(Parent);
fprintf(FileOut, "[%d] LEVEL: %d\n", Parent, Level);
if (Level) { fprintf(FileOut, "ANCESTORS: %d", Ancestors[0]);
for (i = 1; i < Level; i++) fprintf(FileOut, ",%d", Ancestors[i]); } else fprintf(FileOut, "ANCESTORS: None");
fprintf(FileOut, "\nDESCENDANTS: %d\n", CptDescendants[Parent]);
strcpy_s(format, "%lld"); PrintDescendants(Parents[Parent]);
fprintf(FileOut, "\n\n"); totDesc += CptDescendants[Parent]; }
fprintf(FileOut, "Total descendants %d\n\n", totDesc); fprintf(FileOut, "Duration %d seconds", clock()/CLK_TCK); if (fclose(FileOut)) return 1;
return 0; }
void GetChildren(short level, short sum, long long product) { if (Primes[level+1]) GetChildren(level+1, sum, product);
sum += Primes[level];
while (sum <= MAXPARENT) { product *= Primes[level];
if (sum > Primes[level]) { Parents[sum] = InsertChild(Parents[sum], product); CptDescendants[sum]++; }
if (Primes[level+1]) GetChildren(level+1, sum, product);
sum += Primes[level]; } }
struct Children *InsertChild(struct Children *node, long long child) { if (node) { if (child <= node->Child) node->pLeft = InsertChild(node->pLeft, child); else node->pRight = InsertChild(node->pRight, child); } else { if (node = (struct Children *) malloc(sizeof(Children))) { node->Child = child; node->pLeft = 0; node->pRight = 0; } }
return node; }
short GetAncestors(short child) { short Child = child; short Parent = 0; short Index = 0;
while (Child > 1) { while (Child % Primes[Index] == 0) { Child /= Primes[Index]; Parent += Primes[Index]; }
Index++; }
if (Parent == child || child == 1) return 0;
Index = GetAncestors(Parent);
Ancestors[Index] = Parent; return ++Index; }
void PrintDescendants(struct Children *node) { if (node->pLeft) PrintDescendants(node->pLeft);
fprintf(FileOut, format, node->Child); strcpy_s(format, ",%lld");
if (node->pRight) PrintDescendants(node->pRight);
free(node); return; }
int GetPrimes(int primes[], int maxPrime, int nbrPrimes) { int Index = 0; int Max;
if (maxPrime < 2 && nbrPrimes < 1) return false;
int Value = 1; primes[Index] = 2;
while ((Value += 2) <= maxPrime || Index < nbrPrimes-1) { Max = (int) floor(sqrt((double) Value));
for (int i = 0; i <= Index; i++) { if (primes[i] > Max) { if (++Index >= NBRPRIMES) return false;
primes[Index] = Value; break; }
if (Value % primes[i] == 0) break; } }
return ++Index; } </lang>
Visual Basic .NET
Visual Basic .NET with tables
The solution with tables is fast, but you have to know how many items have to be reserved for the tables. <lang vbnet>Imports System.Math
Module Module1
Const MAXPRIME = 99 ' greatest prime number Const MAXPARENT = 99 ' greatest parent number
Const NBRPRIMES = 30 ' number of primes Const NBRCHILDREN = 547000 ' number of children (total descendants) Const NBRDESCENDANTS = 38300 ' number of descendants (per parent) Const NBRANCESTORS = 10 ' number of parent's ancestors
Public Primes(NBRPRIMES + 1) As Integer ' table of the prime number Public Parents(MAXPARENT + 1) As Integer ' index table of the first descendant found (per parent) Public CptDescendants(MAXPARENT + 1) As Integer ' counter table of the number of descendants (per parent) Public Ancestors(NBRANCESTORS) As Short ' table of the parent's ancestors Public Descendants(NBRDESCENDANTS) As Long ' table of one parent's descendants Public Children(NBRCHILDREN) As ChildStruct Public iChild As Integer
Public Structure ChildStruct Public Child As Long Public pLeft As Integer Public pRight As Integer End Structure
Sub Main() Dim StartTime As Date = Now Dim Duration As Long Dim Parent As Short Dim Level As Short Dim i As Integer Dim iDesc As Integer Dim totDesc As Integer = 0
If GetPrimes(Primes, MAXPRIME) = 0 Then Return End If
GetChildren(0, 0, 1)
If MAXPARENT > MAXPRIME Then If GetPrimes(Primes, MAXPARENT) = 0 Then Return End If End If
FileOpen(1, "Ancestors1.txt", OpenMode.Output) ' Open file for output.
For Parent = 5 To MAXPARENT Level = GetAncestors(Parent) PrintLine(1, "[" & Parent.ToString & "] LEVEL: " & Level.ToString)
If Level > 0 Then Print(1, "ANCESTORS: " & Ancestors(0).ToString) For i = 1 To Level - 1 Print(1, "," & Ancestors(i).ToString) Next PrintLine(1) Else PrintLine(1, "ANCESTORS: None") End If
PrintLine(1, "DESCENDANTS: " & CptDescendants(Parent).ToString) iDesc = 0 GetDescendants(Parents(Parent), iDesc)
Print(1, Descendants(0).ToString) For i = 1 To CptDescendants(Parent) - 1 Print(1, "," & Descendants(i).ToString) Next
PrintLine(1) PrintLine(1) totDesc += CptDescendants(Parent) Next PrintLine(1, "Total descendants " & totDesc.ToString) PrintLine(1) Duration = DateDiff(DateInterval.Second, StartTime, Now) PrintLine(1, "Duration " & Duration.ToString & " seconds") FileClose(1) End Sub Function GetChildren(_level As Short, _sum As Short, _product As Long) As Object If Primes(_level + 1) Then GetChildren(_level + 1, _sum, _product) End If
_sum += Primes(_level)
Do While _sum <= MAXPARENT _product *= Primes(_level)
If _sum > Primes(_level) Then If Parents(_sum) Then InsertChild(Parents(_sum), _product) Else Parents(_sum) = InsertChild(Parents(_sum), _product) End If CptDescendants(_sum) += 1 End If
If Primes(_level + 1) Then GetChildren(_level + 1, _sum, _product) End If
_sum += Primes(_level) Loop Return Nothing End Function Function InsertChild(_index As Integer, _child As Long) As Integer If _index Then If _child <= Children(_index).Child Then If Children(_index).pLeft Then InsertChild(Children(_index).pLeft, _child) Else Children(_index).pLeft = InsertChild(Children(_index).pLeft, _child) End If Else If Children(_index).pRight Then InsertChild(Children(_index).pRight, _child) Else Children(_index).pRight = InsertChild(Children(_index).pRight, _child) End If End If Else iChild += 1 Children(iChild).Child = _child Children(iChild).pLeft = 0 Children(iChild).pRight = 0 End If
Return iChild End Function Function GetAncestors(_child As Short) As Short Dim Child As Short = _child Dim Index As Short = 0 Dim Parent As Short = 0
Do While Child > 1 Do While Child Mod Primes(Index) = 0 Child /= Primes(Index) Parent += Primes(Index) Loop Index += 1 Loop
If Parent = _child Or _child = 1 Then Return 0 End If
Index = GetAncestors(Parent) Ancestors(Index) = Parent Return Index + 1 End Function Function GetDescendants(_index As Integer, _ind As Integer) As Integer If Children(_index).pLeft Then _ind = GetDescendants(Children(_index).pLeft, _ind) End If
Descendants(_ind) = Children(_index).Child _ind += 1
If Children(_index).pRight Then _ind = GetDescendants(Children(_index).pRight, _ind) End If Return _ind End Function Function GetPrimes(_primes() As Integer, Optional _maxPrime As Integer = 0, Optional _nbrPrimes As Integer = 0) As Integer Dim Index As Integer Dim Value As Integer Dim i As Integer Dim Max As Integer
If _maxPrime < 2 And _nbrPrimes < 1 Then Return vbFalse End If
Index = 0 _primes(Index) = 2 Value = 3
While Value <= _maxPrime Or Index < _nbrPrimes - 1 Max = Floor(Sqrt(Value))
For i = 0 To Index If _primes(i) > Max Then Index += 1
If Index >= NBRPRIMES Then Return vbFalse End If
_primes(Index) = Value Exit For End If
If Value Mod _primes(i) = 0 Then Exit For End If Next Value += 2 End While Return Index + 1 End Function
End Module</lang>
Visual Basic .NET with 1 collection
This solution is very slow. One table, only, has been replaced by one collection (the Primes tabel). <lang vbnet>Imports System.Math
Module Module1
Const MAXPRIME = 99 ' greatest prime number Const MAXPARENT = 99 ' greatest parent number
Const NBRCHILDREN = 547000 ' number of children (total descendants) Const NBRDESCENDANTS = 38300 ' number of descendants (per parent)
Public Primes As Object ' table of the prime numbers Public Parents(MAXPARENT + 1) As Integer ' index table of the first descendant found (per parent) Public CptDescendants(MAXPARENT + 1) As Integer ' counter table of the number of descendants (per parent) Public Ancestors As New Collection() ' table of the parent's ancestors Public Descendants(NBRDESCENDANTS) As Long ' table of one parent's descendants Public Children(NBRCHILDREN) As ChildStruct Public iChild As Integer
Public Structure ChildStruct Public Child As Long Public pLeft As Integer Public pRight As Integer End Structure
Sub Main() Dim StartTime As Date = Now Dim Duration As Long Dim Parent As Short Dim i As Integer Dim iDesc As Integer Dim totDesc As Integer = 0
If GetPrimes(Primes, MAXPRIME) = vbFalse Then Return End If
GetChildren(1, 0, 1)
If MAXPARENT > MAXPRIME Then If GetPrimes(Primes, MAXPARENT) = vbFalse Then Return End If End If
FileOpen(1, "Ancestors1.txt", OpenMode.Output) ' Open file for output.
For Parent = 5 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) Else PrintLine(1, "ANCESTORS: None") End If
PrintLine(1, "DESCENDANTS: " & CptDescendants(Parent).ToString) iDesc = 0 GetDescendants(Parents(Parent), iDesc) Print(1, Descendants(0).ToString) For i = 1 To CptDescendants(Parent) - 1 Print(1, "," & Descendants(i).ToString) Next PrintLine(1) PrintLine(1) totDesc += CptDescendants(Parent) Ancestors.Clear() Next PrintLine(1, "Total descendants " & totDesc.ToString) PrintLine(1) Duration = DateDiff(DateInterval.Second, StartTime, Now) PrintLine(1, "Duration " & Duration.ToString & " seconds") FileClose(1) End Sub Function GetChildren(_level As Short, _sum As Short, _product As Long) If _level < Primes.count Then GetChildren(_level + 1, _sum, _product) End If
Dim Prime = Primes.item(_level) _sum += Prime
While _sum <= MAXPARENT _product *= Prime
If _sum > Prime Then If Parents(_sum) Then InsertChild(Parents(_sum), _product) Else Parents(_sum) = InsertChild(Parents(_sum), _product) End If
CptDescendants(_sum) += 1 End If
If _level < Primes.count Then GetChildren(_level + 1, _sum, _product) End If
_sum += Prime End While Return Nothing End Function Function InsertChild(_index As Integer, _child As Long) As Integer If _index Then If _child <= Children(_index).Child Then If Children(_index).pLeft Then InsertChild(Children(_index).pLeft, _child) Else Children(_index).pLeft = InsertChild(Children(_index).pLeft, _child) End If Else If Children(_index).pRight Then InsertChild(Children(_index).pRight, _child) Else Children(_index).pRight = InsertChild(Children(_index).pRight, _child) End If End If Else iChild += 1 Children(iChild).Child = _child Children(iChild).pLeft = 0 Children(iChild).pRight = 0 End If
Return iChild 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 GetDescendants(_index As Integer, _ind As Integer) As Integer If Children(_index).pLeft Then _ind = GetDescendants(Children(_index).pLeft, _ind) End If
Descendants(_ind) = Children(_index).Child _ind += 1
If Children(_index).pRight Then _ind = GetDescendants(Children(_index).pRight, _ind) End If
Return _ind End Function Function GetPrimes(ByRef _primes As Object, Optional _maxPrime As Integer = 2, Optional _nbrPrimes As Integer = 1) As Boolean Dim Value As Integer Dim Max As Integer Dim Prime As Integer
If _maxPrime < 2 And _nbrPrimes < 1 Then Return vbFalse End If
_primes = New Collection() _primes.Add(2) Value = 3 While Value <= _maxPrime Or _primes.count < _nbrPrimes 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</lang>