「多倍長整数のビット表現でエラトステネス」をC++にした。うーん。普通に「配列でエラトステネス」とかのほうが早いのかもしれん。

#include <stdio.h>
#include <iostream>
#include <math.h>

#include <NTL/ZZ.h>

ZZ zebraBit(unsigned long span, ZZ length){
  unsigned long i;
  ZZ base, bit;
  base = 2;
  bit = power(base, (span - 1));
  
  for (i = 1; i < (length/span) + 1; i++){
    bit = LeftShift(power(base, (span - 1)), (i * span)) | bit;
  }

  return bit;
}

void binArray2intList(ZZ intasbin, unsigned long mistery){
  ZZ num, mistery_base, shift_base;
  unsigned long count;

  count = 0;
  shift_base = 1;
  mistery_base = 2;
  num = intasbin;

  while (num > power(mistery_base, mistery)){
    if ((intasbin & LeftShift(shift_base, count)) > 0){
      ;
    }else{
      cout << count + 1 << "\n";
    }
    num = RightShift(num, 1);
    count = count + 1;
  }
}

int main(){
  unsigned long i, sqrt_order;
  ZZ bit, shift_base, order;
  bit = 0;
  shift_base = 1;

  order = 100000;
  sqrt_order = 317;

  for (i = 2; i < sqrt_order; i++){
    bit = zebraBit(i, order) - LeftShift(shift_base, i - 1) | bit;
  }
  binArray2intList(bit, sqrt_order);
}

コンパイルと実行。

$ gcc ntl_test.cc -lstdc++ -lntl
$ time ./a.out > result.txt

real    0m18.692s
user    0m18.230s
sys     0m0.020s

misteryは、ミステリー。なんか、ビットシフトがうまくいかないので補正。っていうか、そんなことやってるからオーバーヘッドになってるっぽい。そして。しょせんNTLの使い方メモくらいにしかならないのであった。