Sieve of Pritchard: Difference between revisions
New post.
(Created Nim solution.) |
(New post.) |
||
Line 385:
Here, <code>pr 150</code> gives the same result as <code>pritchard 150</code> but <code>pr 1e7</code> takes well under a second.
=={{header|Java}}==
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;
public final class SieveOfPritchard {
public static void main(String[] args) {
System.out.println(sieveOfPritchard(150) + System.lineSeparator());
System.out.println("Number of primes up to 1,000,000 is " + sieveOfPritchard(1_000_000).size() + ".");
System.out.println();
final long start = System.currentTimeMillis();
System.out.print("Number of primes up to 100,000,000 is " + sieveOfPritchard(100_000_000).size());
final long finish = System.currentTimeMillis();
System.out.println(". Obtained in a time of " + ( (double) finish - start ) / 1_000 + " seconds.");
}
private static List<Integer> sieveOfPritchard(int limit) {
List<Integer> primes = new ArrayList<Integer>();
BitSet members = new BitSet(limit + 1);
members.set(1);
List<Integer> deletions = new ArrayList<Integer>();
final int rootLimit = (int) Math.sqrt(limit);
int nLimit = 2;
int stepLength = 1;
int prime = 2;
while ( prime <= rootLimit ) {
if ( stepLength < limit ) {
for ( int w = 1; w >= 0; w = members.nextSetBit(w + 1) ) {
int n = w + stepLength;
while ( n <= nLimit ) {
members.set(n);
n += stepLength;
}
}
stepLength = nLimit;
}
deletions.clear();
int nextPrime = 5;
for ( int w = 1; w < nLimit; w = members.nextSetBit(w + 1) ) {
if ( nextPrime == 5 && w > prime ) {
nextPrime = w;
}
final int n = prime * w;
if ( n > nLimit ) {
break;
}
deletions.add(n);
}
for ( int deletion : deletions ) {
members.clear(deletion);
}
if ( nextPrime < prime ) {
break;
}
primes.add(prime);
prime = ( prime == 2 ) ? 3 : nextPrime;
nLimit = (int) Math.min((long) stepLength * prime, limit);
}
if ( stepLength < limit ) {
for ( int w = 1; w >= 0; w = members.nextSetBit(w + 1) ) {
int n = w + stepLength;
while ( n <= limit ) {
members.set(n);
n += stepLength;
}
}
}
members.clear(1);
for ( int i = members.nextSetBit(0); i >= 0; i = members.nextSetBit(i + 1) ) {
primes.add(i);
};
return primes;
}
}
</syntaxhighlight>
{{ out }}
<pre>
[2, 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]
Number of primes up to 1,000,000 is 78498.
Number of primes up to 100,000,000 is 5761455. Obtained in a time of 0.648 seconds.
</pre>
=={{header|Julia}}==
| |||