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

  显示原文与译文双语对照的内容
100 5

我们知道,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 +"");
时间:原作者:0个回答

68 1

你不需要向 array 中添加所有可能的候选项。你可以创建一个集合来存储所有非素数。

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

 public void primesTo1000() {
 Set<Integer> notPrimes = new HashSet<>();
 ArrayList<Integer> 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<Integer> primes, Set<Integer> notPrimes) {
 if (!notPrimes.contains(k)) {
 primes.add(k);
 for (int j = k * k; j <= 1000; j += k) {
 notPrimes.add(j);
 }
 }
 }

未测试的代码,检查角

下面是在中建议的sieve的包装版本@Will Ness引用。这里版本返回一个素数列表,而不是返回第n 个素数:

public List<Integer> primesTo(int n) {
 List<Integer> 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;
}

在更新的代码中似乎有一个使用布尔 array ( 它并没有返回所有的素数)的Bug 。

public static List<Integer> 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<Integer> primesList = new ArrayList<>();
 for (int i = 0; i <= n; i++)
 if (primes[i])
 primesList.add(i);
 return primesList;
}
public static List<Integer> bitPacking(int n) {
 List<Integer> 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<Integer> 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<Integer> 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
原作者:
...