问如何使用6*k +- 1规则生成素数
EN

Stack Overflow用户

提问于 2015-08-05 08:16:31

回答 7查看 5.8K关注 0票数 21

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

6 * k + 1
6 * k - 1

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

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

为了消除这些条件，我采用了筛分法，去掉了从上述公式中产生的数的因素。

利用事实：

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

因为我们可以用上面的公式生成所有的素数。
如果我们能除去以上数字的所有倍数，我们就只剩下素数了。

生成低于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);

然而，这种方法确实正确地生成素数。这是一个更快的方式，因为我们不需要检查所有的数字，我们在一个筛子中检查。

我的问题是我错过了什么案子吗？这样会好得多，但我从没见过有人在用这个。我做错了什么吗？

这种方法是否可以进行更多的优化？

使用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 + " ");

java

optimization

primes

sieve

回答 7

Stack Overflow用户

发布于 2015-08-05 08:24:47

有几件事情是可以优化的。

首先，在一个removeAll上的“ArrayList”和“ArrayList”操作是相当昂贵的操作(前者是线性的，最坏的是二次型的)，因此您可能不想为此使用ArrayList。哈希或TreeSet在这方面有更好的复杂性，它几乎是常数(哈希复杂性很奇怪)，并且是对数的，我认为。

如果你想要一个更有效的筛子，你可以看看埃拉托斯提尼的筛子，但这不是你关于6k +-1的问题的重点。它略高于您的解决方案，但内存开销并不明显，但速度要快得多。

票数 2

Stack Overflow用户

发布于 2015-08-05 08:45:42

这种方法是否可以进行更多的优化？

答案是肯定的。

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

阅读生成素数

...Furthermore，基于筛子形式，构造了一些整数序列(OEIS中的序列A240673 )，它们也可以用于在一定的区间内生成素数。

这一段的意思是，您从减少整数列表开始的方法确实被学院采用了，但是它们的技术更有效率(当然也更复杂)。

票数 1

Stack Overflow用户

发布于 2015-08-05 12:15:30

你可以用一个轮子生成你的试数，交替添加2和4，这样就消除了6*k +/- 1中的乘法运算。

public void primesTo1000() {
  Set<Integer> notPrimes = new HashSet<>();
  ArrayList<Integer> 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);
}