筛选优化

Question

从自然数序列创建序列:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

除去每2在数第2步:

1 3 5 7 9 11 13 15 17 19 21 23

删除第3步中的每个第3个数字(从上一个序列开始):

1 3 7 9 13 15 19 21 

删除第4步中的每4个数字(从上一个序列开始):

1 3 7 13 19

等等...现在,我们可以说,序列的第4个数字将是13.

这里有定义和正确的解决方案:http://oeis.org/A000960

我的任务是找到序列的第1000个成员.我已经为此编写了一个算法,但我觉得它很慢(当我尝试使用第10,000个成员时需要大约13秒).它的作用是:

• 我number每步增加2,因为我们知道没有偶数.

• 在counters数组中,我存储每个步骤的索引.如果数字是第x步中的xth,我必须删除它,例如第3步中的数字5.我为下一步启动了一个计数器.

  ArrayList<Long> list = new ArrayList<Long>(10000);
  long[] counters = new long[1002];
  long number = -1;
  int active_counter = 3;
  boolean removed;
  counters[active_counter] = 1;
  int total_numbers = 1;
  
  while (total_numbers <= 1000) {
      number += 2;
      removed = false;
      for (int i = 3; i <= active_counter; i++) {
          if ((counters[i] % i) == 0) {
              removed = true;
              if (i == active_counter) {
                  active_counter++;
                  counters[active_counter] = i;
              }
              counters[i]++;
              break;
          }
          counters[i]++;
      }
      if (!removed) {
          list.add(number);
          total_numbers++;
      }
  }
  

Answer 1

您到 OEIS 的链接为我们提供了一些快速计算的方法（公式等）

第二个的实现：

function Flavius(n: Integer): Integer;
var
  m, i: Integer;
begin
  m := n * n;
  for i := n - 1 downto 1 do
    m := (m - 1) - (m - 1) mod i;
  Result := m;
end;

PS 算法是线性的 (O(n))，n=10000 的结果是 78537769