Ulam numbers: Difference between revisions
Content added Content deleted
(Added Rust solution) |
(Added Swift solution) |
||
Line 377: | Line 377: | ||
| otherwise = False</lang> |
| otherwise = False</lang> |
||
=={{header|Java}}== |
|||
<lang java>public class UlamNumbers { |
|||
public static void main(String[] args) { |
|||
long start = System.currentTimeMillis(); |
|||
for (int n = 1; n <= 100000; n *= 10) { |
|||
System.out.println(String.format("Ulam(%d) = %d", n, ulam(n))); |
|||
} |
|||
long finish = System.currentTimeMillis(); |
|||
System.out.println("Elapsed time: " + (finish - start)/1000.0); |
|||
} |
|||
private static int ulam(int n) { |
|||
int[] ulams = new int[Math.max(n, 2)]; |
|||
ulams[0] = 1; |
|||
ulams[1] = 2; |
|||
int sieveLength = 2; |
|||
int[] sieve = new int[sieveLength]; |
|||
sieve[0] = sieve[1] = 1; |
|||
for (int u = 2, ulen = 2; ulen < n; ) { |
|||
sieveLength = u + ulams[ulen - 2]; |
|||
sieve = extend(sieve, sieveLength); |
|||
for (int i = 0; i < ulen - 1; ++i) |
|||
++sieve[u + ulams[i] - 1]; |
|||
for (int i = u; i < sieveLength; ++i) { |
|||
if (sieve[i] == 1) { |
|||
u = i + 1; |
|||
ulams[ulen++] = u; |
|||
break; |
|||
} |
|||
} |
|||
} |
|||
return ulams[n - 1]; |
|||
} |
|||
private static int[] extend(int[] array, int minLength) { |
|||
if (minLength <= array.length) |
|||
return array; |
|||
int newLength = 2 * array.length; |
|||
while (newLength < minLength) |
|||
newLength *= 2; |
|||
int[] newArray = new int[newLength]; |
|||
System.arraycopy(array, 0, newArray, 0, array.length); |
|||
return newArray; |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
Ulam(1) = 1 |
|||
Ulam(10) = 18 |
|||
Ulam(100) = 690 |
|||
Ulam(1000) = 12294 |
|||
Ulam(10000) = 132788 |
|||
Ulam(100000) = 1351223 |
|||
Elapsed time: 9.019 |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |