Ulam numbers: Difference between revisions
Content deleted Content added
m →{{header|Wren}}: Minor tidy |
Ada version! |
||
Line 167: | Line 167: | ||
<pre> |
<pre> |
||
1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99 102 106 114 126 131 138 145 148 155 175 ... |
1 2 3 4 6 8 11 13 16 18 26 28 36 38 47 48 53 57 62 69 72 77 82 87 97 99 102 106 114 126 131 138 145 148 155 175 ... |
||
</pre> |
|||
=={{header|Ada}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="ada">pragma Ada_2022; -- enables Ada 2022 features |
|||
-- Ada has a lot of safety checks that are turned on by default. |
|||
-- It is possible to turn them off, especially when you know they aren't needed, |
|||
-- but this should be done only when you've done your homework. |
|||
-- Turning this one off makes the program nearly 30x slower on my machine; |
|||
-- you may want to see how it works differently on yours. |
|||
pragma Suppress (All_Checks); |
|||
-- pragma Suppress (Tampering_Check); |
|||
with Ada.Containers.Vectors; |
|||
with Ada.Real_Time; |
|||
use all type Ada.Real_Time.Time_Span; -- makes Time_Span's operators public |
|||
with Ada.Text_IO; |
|||
procedure Ulam_Numbers is |
|||
package IO renames Ada.Text_IO; |
|||
package IntVecs is new Ada.Containers.Vectors |
|||
(Index_Type => Positive, Element_Type => Natural); |
|||
subtype IntVec is IntVecs.Vector; |
|||
Something_Went_Wrong : exception; |
|||
function Ulam (Nth : Positive) return Positive is |
|||
Numbers, Sieve : IntVec; |
|||
Ith : Positive := 2; |
|||
begin |
|||
-- initialize |
|||
Numbers.Append (1); |
|||
Numbers.Append (2); |
|||
Sieve.Append (1); |
|||
Sieve.Append (1); |
|||
-- main loop |
|||
while Positive (Numbers.Length) < Nth loop |
|||
declare |
|||
Old_Length : constant Positive := Positive (Sieve.Length) + 1; |
|||
Extend_To : constant Positive := |
|||
Ith + Numbers (Numbers.Last_Index); |
|||
begin |
|||
-- extend sieve |
|||
Sieve.Set_Length (Ada.Containers.Count_Type (Extend_To)); |
|||
for Jth in Old_Length .. Extend_To loop |
|||
Sieve (Jth) := 0; |
|||
end loop; |
|||
for Number of Numbers loop |
|||
Sieve (Ith + Number) := Sieve (Ith + Number) + 1; |
|||
end loop; |
|||
Sieve (Ith + Numbers.Last_Element) := |
|||
Sieve (Ith + Numbers.Last_Element) - 1; |
|||
Ith := Sieve.Find_Index (1, Ith + 1); |
|||
if Ith > Positive (Sieve.Length) then |
|||
raise Something_Went_Wrong with "Iteration" & Ith'Image; |
|||
end if; |
|||
Numbers.Append (Ith); |
|||
end; |
|||
end loop; |
|||
return Numbers.Last_Element; |
|||
end Ulam; |
|||
Start, Stop : Ada.Real_Time.Time; |
|||
Total_Time : Ada.Real_Time.Time_Span := Ada.Real_Time.Time_Span_Zero; |
|||
Entries_To_Compute : constant array (Positive range <>) of Integer := |
|||
[10, 100, 1_000, 10_000, 100_000]; |
|||
begin |
|||
Start := Ada.Real_Time.Clock; |
|||
for Ith of Entries_To_Compute loop |
|||
IO.Put_Line ("The" & Ith'Image & "th Ulam number is" & Ulam (Ith)'Image); |
|||
end loop; |
|||
Stop := Ada.Real_Time.Clock; |
|||
Total_Time := (@ + Stop) - Start; |
|||
IO.Put_Line ("Elapsed time: " & Total_Time'Image); |
|||
end Ulam_Numbers; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The 10th Ulam number is 18 |
|||
The 100th Ulam number is 690 |
|||
The 1000th Ulam number is 12294 |
|||
The 10000th Ulam number is 132788 |
|||
The 100000th Ulam number is 1351223 |
|||
Elapsed time: 20.473358675 |
|||
</pre> |
</pre> |
||