如何使用6 * k + – 1规则生成Primes

我们知道可以使用以下方法生成3以上的所有素数：

6 * k + 1 6 * k - 1 

然而，我们从上面的公式生成的所有数字都不是素数。

 For Example: 6 * 6 - 1 = 35 which is clearly divisible by 5. 

为了消除这些条件，我使用Sieve方法并删除了数字，这些数字是从上面公式生成的数字的因子。

使用事实：

如果一个数字没有素数因素，那么它就是素数。

1. 因为我们可以使用上面的公式生成所有素数。
2. 如果我们可以删除上述数字的所有倍数，我们只剩下素数。

生成低于1000的素数。

 ArrayList 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  0; j += k) { primes[j] = false; } } } for (int i = 0; i <= n; i++) if (primes[i]) System.out.print(i + " "); 

Answer 1

您不需要将所有可能的候选项添加到数组中。 您可以创建一个Set来存储所有非素数。

你也可以开始检查k * k ，而不是2 * k

  public void primesTo1000() { Set notPrimes = new HashSet<>(); ArrayList primes = new ArrayList<>(); primes.add(2);//explicitly add primes.add(3);//2 and 3 for (int i = 1; i < (1000 / 6); i++) { handlePossiblePrime(6 * i - 1, primes, notPrimes); handlePossiblePrime(6 * i + 1, primes, notPrimes); } System.out.println(primes); } public void handlePossiblePrime( int k, List primes, Set notPrimes) { if (!notPrimes.contains(k)) { primes.add(k); for (int j = k * k; j <= 1000; j += k) { notPrimes.add(j); } } } 

未经测试的代码，检查角落

---

这是@Will Ness引用的答案中建议的筛子的一点包装版本。 而不是返回第n _个素数，此版本返回n的素数列表：

 public List primesTo(int n) { List primes = new ArrayList<>(); if (n > 1) { int limit = (n - 3) >> 1; int[] sieve = new int[(limit >> 5) + 1]; for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++) if ((sieve[i >> 5] & (1 << (i & 31))) == 0) { int p = i + i + 3; for (int j = (p * p - 3) >> 1; j <= limit; j += p) sieve[j >> 5] |= 1 << (j & 31); } primes.add(2); for (int i = 0; i <= limit; i++) if ((sieve[i >> 5] & (1 << (i & 31))) == 0) primes.add(i + i + 3); } return primes; } 

---

你的更新代码中似乎有一个使用布尔数组的错误（它没有返回所有的素数）。

 public static List booleanSieve(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 = 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; } } } List primesList = new ArrayList<>(); for (int i = 0; i <= n; i++) if (primes[i]) primesList.add(i); return primesList; } public static List bitPacking(int n) { List primes = new ArrayList<>(); if (n > 1) { int limit = (n - 3) >> 1; int[] sieve = new int[(limit >> 5) + 1]; for (int i = 0; i <= (int) (Math.sqrt(n) - 3) >> 1; i++) if ((sieve[i >> 5] & (1 << (i & 31))) == 0) { int p = i + i + 3; for (int j = (p * p - 3) >> 1; j <= limit; j += p) sieve[j >> 5] |= 1 << (j & 31); } primes.add(2); for (int i = 0; i <= limit; i++) if ((sieve[i >> 5] & (1 << (i & 31))) == 0) primes.add(i + i + 3); } return primes; } public static void main(String... args) { Executor executor = Executors.newSingleThreadExecutor(); executor.execute(() -> { for (int i = 0; i < 10; i++) { int n = (int) Math.pow(10, i); Stopwatch timer = Stopwatch.createUnstarted(); timer.start(); List result = booleanSieve(n); timer.stop(); System.out.println(result.size() + "\tBoolean: " + timer); } for (int i = 0; i < 10; i++) { int n = (int) Math.pow(10, i); Stopwatch timer = Stopwatch.createUnstarted(); timer.start(); List result = bitPacking(n); timer.stop(); System.out.println(result.size() + "\tBitPacking: " + timer); } }); } 

---

 0 Boolean: 38.51 μs 4 Boolean: 45.77 μs 25 Boolean: 31.56 μs 168 Boolean: 227.1 μs 1229 Boolean: 1.395 ms 9592 Boolean: 4.289 ms 78491 Boolean: 25.96 ms 664116 Boolean: 133.5 ms 5717622 Boolean: 3.216 s 46707218 Boolean: 32.18 s 0 BitPacking: 117.0 μs 4 BitPacking: 11.25 μs 25 BitPacking: 11.53 μs 168 BitPacking: 70.03 μs 1229 BitPacking: 471.8 μs 9592 BitPacking: 3.701 ms 78498 BitPacking: 9.651 ms 664579 BitPacking: 43.43 ms 5761455 BitPacking: 1.483 s 50847534 BitPacking: 17.71 s 

Answer 2

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预热，并打印列表的大小并更改n的大小以尝试防止过多的分支预测优化。通过使用+= 6您还可以在所有三种方法中获得更快的速度+= 6在初始种子中，而不是prod6k ：

 import java.util.*; public class PrimeGenerator { public static List generatePrimesArrayList(int n) { List 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 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 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 generatePrimesLinkedList(int n) { List 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 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 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 

Answer 3

有几件事可以优化。

对于初学者来说，ArrayList上的“contains”和“removeAll”操作是相当昂贵的操作（前者是线性的，后者是最差的二次方），所以你可能不想为此使用ArrayList。 Hash或TreeSet具有更好的复杂性，几乎不变（哈希复杂度很奇怪）和对数我认为

如果你想要一个更有效的筛子altogeter，你可以看看Eratosthenes的筛子筛，但这将是你的问题关于6k + -1技巧的问题。 它比您的解决方案略微但并不显着更昂贵，但速度更快。

Answer 4

这种方法可以更加优化吗？

答案是肯定的。

我首先要说的是 ，在一定范围内对数字子集使用筛子是个好主意，而你的建议正是这样做的。

阅读有关生成Primes的信息 ：

…此外，基于筛子forms，构造了一些整数序列（ OEIS中的序列A240673 ），它们也可以用于在某些间隔中产生质数。

本段的含义是，您从简化的整数列表开始的方法确实被学院采用，但他们的技术更有效（但自然而然，更复杂）。

Answer 5

您可以使用滚轮生成试用编号，交替添加2和4，从而消除6 * k +/- 1中的乘法。

 public void primesTo1000() { Set notPrimes = new HashSet<>(); ArrayList primes = new ArrayList<>(); primes.add(2); //explicitly add primes.add(3); //2 and 3 int step = 2; int num = 5 // 2 and 3 already handled. while (num < 1000) { handlePossiblePrime(num, primes, notPrimes); num += step; // Step to next number. step = 6 - step; // Step by 2, 4 alternately. } System.out.println(primes); } 

Answer 6

可能最适合Eratosthenes筛选的标准数据结构是BitSet 。 这是我的解决方案：

 static BitSet genPrimes(int n) { BitSet primes = new BitSet(n); primes.set(2); // add 2 explicitly primes.set(3); // add 3 explicitly for (int i = 6; i <= n ; i += 6) { // step by 6 instead of multiplication primes.set(i - 1); primes.set(i + 1); } int max = (int) Math.sqrt(n); // don't need to filter multiples of primes bigger than max // this for loop enumerates all set bits starting from 5 till the max // sieving 2 and 3 is meaningless: n*6+1 and n*6-1 are never divisible by 2 or 3 for (int i = primes.nextSetBit(5); i >= 0 && i <= max; i = primes.nextSetBit(i+1)) { // The actual sieve algorithm like in your code for(int j = i * i; j <= n; j += i) primes.clear(j); } return primes; } 

用法：

 BitSet primes = genPrimes(1000); // generate primes up to 1000 System.out.println(primes.cardinality()); // print number of primes // print all primes like {2, 3, 5, ...} System.out.println(primes); // print all primes one per line for(int prime = primes.nextSetBit(0); prime >= 0; prime = primes.nextSetBit(prime+1)) System.out.println(prime); // print all primes one per line using java 8: primes.stream().forEach(System.out::println); 

对于小n值，基于布尔的版本可以更快地工作，但是如果你需要，例如，一百万个素数， BitSet将在几次内胜过它并且实际上正常工作。 这是蹩脚的基准：

 public static void main(String... args) { long start = System.nanoTime(); BitSet res = genPrimes(10000000); long diff = System.nanoTime() - start; System.out.println(res.cardinality() + "\tBitSet Seconds: " + diff / 1e9); start = System.nanoTime(); List result = generatePrimesBoolean(10000000); // from durron597 answer diff = System.nanoTime() - start; System.out.println(result.size() + "\tBoolean Seconds: " + diff / 1e9); } 

输出：

 664579 BitSet Seconds: 0.065987717 664116 Boolean Seconds: 0.167620323 

664579是低于10000000 的正确质数 。

Answer 7

下面的方法显示了如何使用6k +/- 1逻辑查找素数

这是用python 3.6编写的

 def isPrime(n): if(n<=1): return 0 elif(n<4): #2 , 3 are prime return 1 elif(n%2==0): #already excluded no.2 ,so any no. div. by 2 cant be prime return 0 elif(n<9): #5, 7 are prime and 6,8 are excl. in the above step return 1 elif(n%3==0): return 1 f=5 #Till now we have checked the div. of n with 2,3 which means with 4,6,8 also now that is why f=5 r=int(n**.5) #rounding of root n, ie: floor(sqrt(n)) r*r<=n while(f<=r): if(n%f==0): #checking if n has any primefactor lessthan sqrt(n), refer LINE 1 return 0 if(n%(f+2)==0): #remember her we are not incrementing f, see the 6k+1 rule to understand this while loop steps ,you will see that most values of f are prime return 0 f=f+6 return 1 def prime_nos(): counter=2 #we know 2,3 are prime print(2) print(3) #we know 2,3 are prime i=1 s=5 #sum 2+3 t=0 n=int(input("Enter the upper limit( should be > 3: ")) n=(n-1)//6 #finding max. limit(n=6*i+1) upto which I(here n on left hand side) should run while(i