The sieve of Sundaram: Difference between revisions
Content added Content deleted
(→{{header|J}}: more readable) |
(New post.) |
||
Line 813: | Line 813: | ||
15485867 |
15485867 |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java> |
|||
import java.util.ArrayList; |
|||
import java.util.List; |
|||
public final class SieveOfSundaram { |
|||
public static void main(String[] args) { |
|||
List<Integer> primes = sieveOfSundaram(16_000_000); |
|||
System.out.println("The first 100 odd primes generated by the Sieve of Sundaram:"); |
|||
for ( int i = 0; i < 100; i++ ) { |
|||
System.out.print(String.format("%3d%s", primes.get(i), ( i % 10 == 9 ? "\n" :" " ))); |
|||
} |
|||
System.out.println(); |
|||
System.out.println("The 1_000_000th Sundaram prime is " + primes.get(1_000_000 - 1)); |
|||
} |
|||
private static List<Integer> sieveOfSundaram(int limit) { |
|||
List<Integer> primes = new ArrayList<Integer>(); |
|||
if ( limit < 3 ) { |
|||
return primes; |
|||
} |
|||
final int k = ( limit - 3 ) / 2 + 1; |
|||
boolean[] marked = new boolean[k]; |
|||
for ( int i = 0; i < ( (int) Math.sqrt(limit) - 3 ) / 2 + 1; i++ ) { |
|||
int p = 2 * i + 3; |
|||
int s = ( p * p - 3 ) / 2; |
|||
for ( int j = s; j < k; j += p ) { |
|||
marked[j] = true; |
|||
} |
|||
} |
|||
for ( int i = 0; i < k; i++ ) { |
|||
if ( ! marked[i] ) { |
|||
primes.add(2 * i + 3); |
|||
} |
|||
} |
|||
return primes; |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
The first 100 odd primes generated by the Sieve of Sundaram: |
|||
3 5 7 11 13 17 19 23 29 31 |
|||
37 41 43 47 53 59 61 67 71 73 |
|||
79 83 89 97 101 103 107 109 113 127 |
|||
131 137 139 149 151 157 163 167 173 179 |
|||
181 191 193 197 199 211 223 227 229 233 |
|||
239 241 251 257 263 269 271 277 281 283 |
|||
293 307 311 313 317 331 337 347 349 353 |
|||
359 367 373 379 383 389 397 401 409 419 |
|||
421 431 433 439 443 449 457 461 463 467 |
|||
479 487 491 499 503 509 521 523 541 547 |
|||
The 1_000_000th Sundaram prime is 15485867 |
|||
</pre> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |