问题：

如何使用6*k-1规则生成质数？

顾乐心

2023-03-14

我们知道，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);

然而，这种方法确实正确生成质数。这运行得更快，因为我们不需要检查我们在筛子中检查的所有数字。

我的问题是，我是否缺少任何边缘盒？这会好得多，但我从未见过有人使用这个。我做错了什么吗？

这种方法可以更优化吗？

使用布尔值 [] 而不是数组列表要快得多。

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

共有3个答案

轩辕乐邦

2023-03-14

有几件事可以优化。

首先，ArrayList上的“包含”和“删除所有”操作是相当昂贵的操作（前者为线性，后者为最坏情况二次），因此您可能不想为此使用ArrayList。哈希或TreeSet对此有更好的复杂性，几乎是恒定的（哈希复杂性很奇怪）和对数的，我认为

如果你想要一个更有效的筛子集合器，你可以看看埃拉托斯特尼的筛子，但这将是你关于6k-1技巧的问题的重点之外。它比您的解决方案占用的内存稍多，但并不明显，但速度快得多。

南门鸿雪

2023-03-14

无需将所有可能的候选项添加到阵列中。您可以创建一个集合来存储所有非素数。

此外，您可以从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);
      }
    }
  }

未测试的代码，检查转角

这是@Will Ness引用的答案中建议的筛子的一个打包版本。这个版本不是返回第n个素数，而是返回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;
}

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

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

徐学潞

2023-03-14

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个连续数字组成的组:

6 千米 - 3， 6 千 - 2， 6 千 - 1， 6 千， 6 千 1， 6 千 2

如果我们稍微考虑一下，我们得到：

3*（2k-1）、2*（3k-1）、6k-1、6*（k）、6k1、2*（3k1）

在任何一组6个连续的数字中，其中三个将被二整除，其中两个将被三整除。这些正是我们迄今为止删除的数字！因此：

这比筛子的速度也有了很大的提高，因为我们不必添加所有额外的元素来移除它们。这解释了为什么你的算法有效，为什么它不会遗漏任何情况；因为它和筛子完全一样。

无论如何，我同意一旦你生成了质数，你的< code>boolean方法是最快的。我已经使用您的< code>ArrayList方法、您的< code>boolean[]方法以及我自己的方法(使用< code>LinkedList和< code>iterator.remove())建立了一个基准测试(因为在< code>LinkedList中删除很快)。这是我的测试工具的代码。请注意，我运行了12次测试，以确保JVM已经预热，我打印了列表的大小，并更改了< code>n的大小，以防止过多的分支预测优化。您还可以通过在初始种子中使用< code> = 6而不是< code>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

类似资料：

如何使用脚本INTERVAL 1生成？

问题内容：我们正在尝试找到一种语法，以从日期函数的第三个参数生成DAY | WEEK | MONTH选项。您知道在DECLARE中使用什么正确的语法，并且应该将其转换为有效的SQL。问题答案：以下是BigQuery标准SQL 这些都是文字，无法进行参数化而且，您知道-动态SQL尚不可用因此，不幸的是，以下是我今天能想到的唯一解决方案
Perl 6规则如何将参数传递给另一个规则？

在中，如何将参数传递给Perl 6语法？我将参数作为子菜单的一部分传递给规则。我想知道我是如何完全在语法中做到这一点的。假设我有这样的东西：如何将参数从传递到？我没有发现任何例子，关于parens的各种猜测都不起作用。
TraceId 和 SpanId 生成规则

TraceId 生成规则 SOFATracer 通过 TraceId 来将一个请求在各个服务器上的调用日志串联起来，TraceId 一般由接收请求经过的第一个服务器产生，产生规则是：服务器 IP + 产生 ID 时候的时间 + 自增序列 + 当前进程号，比如： 0ad1348f1403169275002100356696 前 8 位 0ad1348f 即产生 TraceId 的机器的 IP，
如何使用Java集成测试调用Drools规则

我正在编写一项规则，以根据申诉的类别确定应接受的服务类型。我写了一个jUnit联调来使用一个新创建的java对象来测试该规则，该对象名为“申诉DTO”。我写了一个服务类来取消规则。 jUnit测试失败。 java.lang.NullPointerException在cm.grievance.rules.规则est.calculate资格（规则est.java:13）我用KieContaine
1. 基本规则

1. 基本规则除了Hello World这种极简单的程序之外，一般的程序都是由多个源文件编译链接而成的，这些源文件的处理步骤通常用Makefile来管理。Makefile起什么作用呢？我们先看一个例子，这个例子由例 12.3 “用深度优先搜索解迷宫问题”改写而成： /* main.c */ #include <stdio.h> #include "main.h" #include "stack.
pandas使用什么规则生成视图与副本？

问题内容：我对Pandas决定从数据框中选择内容是原始数据框的副本或原始数据视图时使用的规则感到困惑。例如，如果我有我了解a会传回副本，因此类似将对原始数据帧无效。我也了解标量或命名切片会返回一个视图，因此对它们的赋值（例如要么会改变。但是当涉及到更复杂的案件时，我迷失了。例如，变化，但是才不是。是否有一个熊猫正在使用的简单规则，我只是想念它？在这些特定情况下发生了什么？尤其是，

如何使用6*k-1规则生成质数？

共有3个答案

相关问答

相关文章

相关阅读

相关工具

相关文档