gpt4 book ai didi

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

转载 作者:IT老高 更新时间:2023-10-28 20:54:06 24 4
gpt4 key购买 nike

我们知道所有大于 3 的素数都可以通过以下方式生成:

6 * k + 1
6 * k - 1

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

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

为了消除这种情况,我使用了筛法并删除了作为上述公式生成的数字的因素的数字。

使用事实:

A number is said to be prime if it has no prime factors.

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

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

最佳答案

5 是您的标准生成的第一个数字。让我们看一下生成的最多 25 个数字:

5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25

现在,让我们看看这些相同的数字,当我们使用埃拉托色尼筛算法时:

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 个连续数字的组中,其中三个可以被 2 整除,其中两个可以被 3 整除。这些正是我们迄今为止删除的数字!因此:

您仅使用 6k - 16k + 1 的算法与前两轮埃拉托色尼筛法完全相同。

与 Sieve 相比,这也是一个相当不错的速度改进,因为我们不必添加所有这些额外的元素来移除它们。这解释了为什么您的算法有效以及为什么它不会遗漏任何情况;因为它和筛子完全一样。


无论如何,我同意一旦你生成了素数,你的 boolean 方式是迄今为止最快的。我已经使用你的 ArrayList 设置了一个基准 方式,您的 boolean[] 方式,以及我自己使用 LinkedListiterator.remove() 的方式(因为删除速度很快在 LinkedList 中。这是我的测试工具的代码。请注意,我运行了 12 次测试以确保 JVM 已预热,我打印列表的大小并更改 n 试图防止过多的 branch prediction 优化。您还可以通过在初始种子中使用 += 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

关于java - 如何使用 6*k +- 1 规则生成素数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31837761/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com