Legendre prime counting function: Difference between revisions
Content added Content deleted
(→{{header|Go}}: Added a third much faster version.) |
GordonBGood (talk | contribs) m (put Java contribution in alphabetic order...) |
||
Line 1,129: | Line 1,129: | ||
Took 1862 microseconds |
Took 1862 microseconds |
||
</pre> |
|||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java">import java.util.*; |
|||
public class LegendrePrimeCounter { |
|||
public static void main(String[] args) { |
|||
LegendrePrimeCounter counter = new LegendrePrimeCounter(1000000000); |
|||
for (int i = 0, n = 1; i < 10; ++i, n *= 10) |
|||
System.out.printf("10^%d\t%d\n", i, counter.primeCount((n))); |
|||
} |
|||
private List<Integer> primes; |
|||
public LegendrePrimeCounter(int limit) { |
|||
primes = generatePrimes((int)Math.sqrt((double)limit)); |
|||
} |
|||
public int primeCount(int n) { |
|||
if (n < 2) |
|||
return 0; |
|||
int a = primeCount((int)Math.sqrt((double)n)); |
|||
return phi(n, a) + a - 1; |
|||
} |
|||
private int phi(int x, int a) { |
|||
if (a == 0) |
|||
return x; |
|||
if (a == 1) |
|||
return x - (x >> 1); |
|||
int pa = primes.get(a - 1); |
|||
if (x <= pa) |
|||
return 1; |
|||
return phi(x, a - 1) - phi(x / pa, a - 1); |
|||
} |
|||
private static List<Integer> generatePrimes(int limit) { |
|||
boolean[] sieve = new boolean[limit >> 1]; |
|||
Arrays.fill(sieve, true); |
|||
for (int p = 3, s = 9; s < limit; p += 2) { |
|||
if (sieve[p >> 1]) { |
|||
for (int q = s; q < limit; q += p << 1) |
|||
sieve[q >> 1] = false; |
|||
} |
|||
s += (p + 1) << 2; |
|||
} |
|||
List<Integer> primes = new ArrayList<>(); |
|||
if (limit > 2) |
|||
primes.add(2); |
|||
for (int i = 1; i < sieve.length; ++i) { |
|||
if (sieve[i]) |
|||
primes.add((i << 1) + 1); |
|||
} |
|||
return primes; |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
10^0 0 |
|||
10^1 4 |
|||
10^2 25 |
|||
10^3 168 |
|||
10^4 1229 |
|||
10^5 9592 |
|||
10^6 78498 |
|||
10^7 664579 |
|||
10^8 5761455 |
|||
10^9 50847534 |
|||
</pre> |
</pre> |
||
Line 1,585: | Line 1,516: | ||
But we can simplify that to p:inv when we know that primes are not being tested. |
But we can simplify that to p:inv when we know that primes are not being tested. |
||
=={{header|Java}}== |
|||
<syntaxhighlight lang="java">import java.util.*; |
|||
public class LegendrePrimeCounter { |
|||
public static void main(String[] args) { |
|||
LegendrePrimeCounter counter = new LegendrePrimeCounter(1000000000); |
|||
for (int i = 0, n = 1; i < 10; ++i, n *= 10) |
|||
System.out.printf("10^%d\t%d\n", i, counter.primeCount((n))); |
|||
} |
|||
private List<Integer> primes; |
|||
public LegendrePrimeCounter(int limit) { |
|||
primes = generatePrimes((int)Math.sqrt((double)limit)); |
|||
} |
|||
public int primeCount(int n) { |
|||
if (n < 2) |
|||
return 0; |
|||
int a = primeCount((int)Math.sqrt((double)n)); |
|||
return phi(n, a) + a - 1; |
|||
} |
|||
private int phi(int x, int a) { |
|||
if (a == 0) |
|||
return x; |
|||
if (a == 1) |
|||
return x - (x >> 1); |
|||
int pa = primes.get(a - 1); |
|||
if (x <= pa) |
|||
return 1; |
|||
return phi(x, a - 1) - phi(x / pa, a - 1); |
|||
} |
|||
private static List<Integer> generatePrimes(int limit) { |
|||
boolean[] sieve = new boolean[limit >> 1]; |
|||
Arrays.fill(sieve, true); |
|||
for (int p = 3, s = 9; s < limit; p += 2) { |
|||
if (sieve[p >> 1]) { |
|||
for (int q = s; q < limit; q += p << 1) |
|||
sieve[q >> 1] = false; |
|||
} |
|||
s += (p + 1) << 2; |
|||
} |
|||
List<Integer> primes = new ArrayList<>(); |
|||
if (limit > 2) |
|||
primes.add(2); |
|||
for (int i = 1; i < sieve.length; ++i) { |
|||
if (sieve[i]) |
|||
primes.add((i << 1) + 1); |
|||
} |
|||
return primes; |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
10^0 0 |
|||
10^1 4 |
|||
10^2 25 |
|||
10^3 168 |
|||
10^4 1229 |
|||
10^5 9592 |
|||
10^6 78498 |
|||
10^7 664579 |
|||
10^8 5761455 |
|||
10^9 50847534 |
|||
</pre> |
|||
=={{header|jq}}== |
=={{header|jq}}== |