Uma*_*nth 20 java optimization primes sieve
我们知道可以使用以下方法生成3以上的所有素数:
6 * k + 1
6 * k - 1
但是,我们从上面的公式生成的所有数字都不是素数.
For Example:
6 * 6 - 1 = 35 which is clearly divisible by 5.
为了消除这些条件,我使用Sieve方法并删除了数字,这些数字是从上面公式生成的数字的因子.
使用事实:
如果没有素数因素,那么一个数字被称为素数.
生成低于1000的素数.
ArrayList<Integer> primes = new ArrayList<>();
primes.add(2);//explicitly add
primes.add(3);//2 and 3
int n = 1000;
for (int i = 1; i <= (n / 6) ; i++) {
//get all the numbers which can be generated by the formula
int prod6k = 6 * i;
primes.add(prod6k - 1);
primes.add(prod6k + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
//remove all the factors of the numbers generated by the formula
for(int j = k * k; j <= n; j += k)//changed to k * k from 2 * k, Thanks to DTing
{
int index = primes.indexOf(j);
if(index != -1)
primes.remove(index);
}
}
System.out.println(primes);
但是,此方法确实正确生成素数.这样运行速度要快得多,因为我们不需要检查我们在Sieve中检查的所有数字.
我的问题是,我错过了任何边缘案例吗？这会好很多但我从未见过有人使用过这个.难道我做错了什么？
这种方法可以更加优化吗？
以一个boolean[]代替ArrayList的速度要快得多.
int n = 100000000;
boolean[] primes = new boolean[n + 1];
for (int i = 0; i <= n; i++)
primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 1; i <= n / 6; i++) {
int prod6k = 6 * i;
primes[prod6k + 1] = true;
primes[prod6k - 1] = true;
}
for (int i = 0; i <= n; i++) {
if (primes[i]) {
int k = i;
for (int j = k * k; j <= n && j > 0; j += k) {
primes[j] = false;
}
}
}
for (int i = 0; i <= n; i++)
if (primes[i])
System.out.print(i + " ");
5是您的标准生成的第一个数字.让我们来看看最多生成25的数字:
5,
6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
现在,让我们看看这些相同的数字,当我们使用Sieve of Eratosthenes算法时:
5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
删除2后:
5,
6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
删除3后:
5,
6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25
这与第一套相同!注意它们都包括25,这不是素数.如果我们考虑一下,这是一个明显的结果.考虑任意一组6个连续数字:
6k - 3,6k - 2,6k - 1,6k,6k + 1,6k + 2
如果我们考虑一点,我们得到:
3*(2k - 1),2*(3k - 1),6k - 1,6*(k),6k + 1,2*(3k + 1)
在任何一组6个连续数字中,其中3个可以被2整除,其中2个可以被3整除.这些正是我们到目前为止删除的数字!因此:
6k - 1和6k + 1前两轮的Erathosthenes筛子完全相同.与Sieve相比,这是一个相当不错的速度提升,因为我们不必添加所有这些额外的元素只是为了删除它们.这解释了为什么你的算法有效以及为什么它不会错过任何情况; 因为它与Sieve完全相同.
无论如何,我同意,一旦你产生素数,你的boolean方式是迄今为止最快的.我已经使用你的ArrayList方式,你的boolean[]方式和我自己的方式使用LinkedList和设置了一个基准测试iterator.remove()(因为删除很快LinkedList.这是我的测试工具的代码.注意我运行测试12次以确保JVM被加热up,我打印列表的大小并更改大小n以尝试防止过多的分支预测优化.通过+= 6在初始种子中使用,您也可以在所有三种方法中获得更快,而不是prod6k:
import java.util.*;
public class PrimeGenerator {
public static List<Integer> generatePrimesArrayList(int n) {
List<Integer> primes = new ArrayList<>(getApproximateSize(n));
primes.add(2);// explicitly add
primes.add(3);// 2 and 3
for (int i = 6; i <= n; i+=6) {
// get all the numbers which can be generated by the formula
primes.add(i - 1);
primes.add(i + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
// remove all the factors of the numbers generated by the formula
for (int j = k * k; j <= n; j += k)// changed to k * k from 2 * k, Thanks
// to DTing
{
int index = primes.indexOf(j);
if (index != -1)
primes.remove(index);
}
}
return primes;
}
public static List<Integer> generatePrimesBoolean(int n) {
boolean[] primes = new boolean[n + 5];
for (int i = 0; i <= n; i++)
primes[i] = false;
primes[2] = primes[3] = true;
for (int i = 6; i <= n; i+=6) {
primes[i + 1] = true;
primes[i - 1] = true;
}
for (int i = 0; i <= n; i++) {
if (primes[i]) {
int k = i;
for (int j = k * k; j <= n && j > 0; j += k) {
primes[j] = false;
}
}
}
int approximateSize = getApproximateSize(n);
List<Integer> primesList = new ArrayList<>(approximateSize);
for (int i = 0; i <= n; i++)
if (primes[i])
primesList.add(i);
return primesList;
}
private static int getApproximateSize(int n) {
// Prime Number Theorem. Round up
int approximateSize = (int) Math.ceil(((double) n) / (Math.log(n)));
return approximateSize;
}
public static List<Integer> generatePrimesLinkedList(int n) {
List<Integer> primes = new LinkedList<>();
primes.add(2);// explicitly add
primes.add(3);// 2 and 3
for (int i = 6; i <= n; i+=6) {
// get all the numbers which can be generated by the formula
primes.add(i - 1);
primes.add(i + 1);
}
for (int i = 0; i < primes.size(); i++) {
int k = primes.get(i);
for (Iterator<Integer> iterator = primes.iterator(); iterator.hasNext();) {
int primeCandidate = iterator.next();
if (primeCandidate == k)
continue; // Always skip yourself
if (primeCandidate == (primeCandidate / k) * k)
iterator.remove();
}
}
return primes;
}
public static void main(String... args) {
int initial = 4000;
for (int i = 0; i < 12; i++) {
int n = initial * i;
long start = System.currentTimeMillis();
List<Integer> result = generatePrimesArrayList(n);
long seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "\tArrayList Seconds: " + seconds);
start = System.currentTimeMillis();
result = generatePrimesBoolean(n);
seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "\tBoolean Seconds: " + seconds);
start = System.currentTimeMillis();
result = generatePrimesLinkedList(n);
seconds = System.currentTimeMillis() - start;
System.out.println(result.size() + "\tLinkedList Seconds: " + seconds);
}
}
}
以及最后几次试验的结果:
3432 ArrayList Seconds: 430
3432 Boolean Seconds: 0
3432 LinkedList Seconds: 90
3825 ArrayList Seconds: 538
3824 Boolean Seconds: 0
3824 LinkedList Seconds: 81
4203 ArrayList Seconds: 681
4203 Boolean Seconds: 0
4203 LinkedList Seconds: 100
4579 ArrayList Seconds: 840
4579 Boolean Seconds: 0
4579 LinkedList Seconds: 111
您不需要将所有可能的候选者添加到数组中。您可以创建一个 Set 来存储所有非素数。
\n\n您也可以开始检查k * k，而不是2 * k
public void primesTo1000() {\n Set<Integer> notPrimes = new HashSet<>();\n ArrayList<Integer> primes = new ArrayList<>();\n primes.add(2);//explicitly add\n primes.add(3);//2 and 3\n\n for (int i = 1; i < (1000 / 6); i++) {\n handlePossiblePrime(6 * i - 1, primes, notPrimes);\n handlePossiblePrime(6 * i + 1, primes, notPrimes);\n }\n System.out.println(primes);\n }\n\n public void handlePossiblePrime(\n int k, List<Integer> primes, Set<Integer> notPrimes) {\n if (!notPrimes.contains(k)) {\n primes.add(k);\n for (int j = k * k; j <= 1000; j += k) {\n notPrimes.add(j);\n }\n }\n }\n未经测试的代码，检查角落
\n\n这是筛子的一个包装版本，如@Will Ness引用的答案中所建议的。此版本不是返回第 n个素数，而是返回 n 的素数列表：
\n\npublic List<Integer> primesTo(int n) {\n List<Integer> primes = new ArrayList<>();\n if (n > 1) {\n int limit = (n - 3) >> 1;\n int[] sieve = new int[(limit >> 5) + 1];\n for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++)\n if ((sieve[i >> 5] & (1 << (i & 31))) == 0) {\n int p = i + i + 3;\n for (int j = (p * p - 3) >> 1; j <= limit; j += p)\n sieve[j >> 5] |= 1 << (j & 31);\n }\n primes.add(2);\n for (int i = 0; i <= limit; i++)\n if ((sieve[i >> 5] & (1 << (i & 31))) == 0)\n primes.add(i + i + 3);\n }\n return primes;\n}\n您更新的代码中似乎存在一个使用布尔数组的错误（它没有返回所有素数）。
\n\npublic static List<Integer> booleanSieve(int n) {\n boolean[] primes = new boolean[n + 5];\n for (int i = 0; i <= n; i++)\n primes[i] = false;\n primes[2] = primes[3] = true;\n for (int i = 1; i <= n / 6; i++) {\n int prod6k = 6 * i;\n primes[prod6k + 1] = true;\n primes[prod6k - 1] = true;\n }\n for (int i = 0; i <= n; i++) {\n if (primes[i]) {\n int k = i;\n for (int j = k * k; j <= n && j > 0; j += k) {\n primes[j] = false;\n }\n }\n }\n\n List<Integer> primesList = new ArrayList<>();\n for (int i = 0; i <= n; i++)\n if (primes[i])\n primesList.add(i);\n\n return primesList;\n}\n\npublic static List<Integer> bitPacking(int n) {\n List<Integer> primes = new ArrayList<>();\n if (n > 1) {\n int limit = (n - 3) >> 1;\n int[] sieve = new int[(limit >> 5) + 1];\n for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++)\n if ((sieve[i >> 5] & (1 << (i & 31))) == 0) {\n int p = i + i + 3;\n for (int j = (p * p - 3) >> 1; j <= limit; j += p)\n sieve[j >> 5] |= 1 << (j & 31);\n }\n primes.add(2);\n for (int i = 0; i <= limit; i++)\n if ((sieve[i >> 5] & (1 << (i & 31))) == 0)\n primes.add(i + i + 3);\n }\n return primes;\n}\n\npublic static void main(String... args) {\n Executor executor = Executors.newSingleThreadExecutor();\n executor.execute(() -> {\n for (int i = 0; i < 10; i++) {\n int n = (int) Math.pow(10, i);\n Stopwatch timer = Stopwatch.createUnstarted();\n timer.start();\n List<Integer> result = booleanSieve(n);\n timer.stop();\n System.out.println(result.size() + "\\tBoolean: " + timer);\n }\n\n for (int i = 0; i < 10; i++) {\n int n = (int) Math.pow(10, i);\n Stopwatch timer = Stopwatch.createUnstarted();\n timer.start();\n List<Integer> result = bitPacking(n);\n timer.stop();\n System.out.println(result.size() + "\\tBitPacking: " + timer);\n }\n });\n}\n0 Boolean: 38.51 \xce\xbcs\n4 Boolean: 45.77 \xce\xbcs\n25 Boolean: 31.56 \xce\xbcs\n168 Boolean: 227.1 \xce\xbcs\n1229 Boolean: 1.395 ms\n9592 Boolean: 4.289 ms\n78491 Boolean: 25.96 ms\n664116 Boolean: 133.5 ms\n5717622 Boolean: 3.216 s\n46707218 Boolean: 32.18 s\n0 BitPacking: 117.0 \xce\xbcs\n4 BitPacking: 11.25 \xce\xbcs\n25 BitPacking: 11.53 \xce\xbcs\n168 BitPacking: 70.03 \xce\xbcs\n1229 BitPacking: 471.8 \xce\xbcs\n9592 BitPacking: 3.701 ms\n78498 BitPacking: 9.651 ms\n664579 BitPacking: 43.43 ms\n5761455 BitPacking: 1.483 s\n50847534 BitPacking: 17.71 s\n| 归档时间： |
|
| 查看次数： |
2065 次 |
| 最近记录： |