Sieve of Pritchard: Difference between revisions
Content added Content deleted
(Created Nim solution.) |
(New post.) |
||
Line 385: | 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. |
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}}== |
=={{header|Julia}}== |