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>