Arduinoを使って1602LCDで高速素数表示をした

素数を数えると精神衛生上によいと聞いたので、
LCDキャラクタディスプレイに素数を表示して冷静になろうと思う。

ミラー-ラビン素数判定法 - Wikipedia

リンク先にあるミラーラビン素数判定法というものを、そのまま実装した。
結果が合っているかの確認はしていないけど、落ち着く可能性はあると思う。

IDEのバージョンは0022で
ボードは"Arduino Pro or Pro Mini (3.3V,8MHz)w/ATmega168"を使用した。

以下ソース

// 高速素数表示、時間付

#include <stdint.h> 
#include <stdio.h>
#include <LiquidCrystal.h>

LiquidCrystal lcd(12, 11, 10, 5, 4, 3, 2);

void setup() {
  randomSeed(analogRead(0));
  lcd.begin(16, 2);
  lcd.clear();
  lcd.setCursor(0, 0);
}

uintmax_t num = 100000UL; // 最初に判定したい数
uint32_t time;
char str[20];

void loop() {
  if (isPrime(num)) {
    time = millis();

    snprintf(str, sizeof(str), "PrimeNum:%7lu", num);
    lcd.setCursor(0, 0);
    lcd.print(str);

    snprintf(str, sizeof(str), "  %02luh%02lum%02lus%03lums",
      time / 1000UL / 3600UL % 24UL, time / 1000UL / 60UL % 60UL,
      time / 1000UL % 60UL, time % 1000UL);
    lcd.setCursor(0, 1);
    lcd.print(str);
  }
  num++;
}


// ミラー・ラビン素数判定法 wikipediaから引用・改変
bool isPrime(const uintmax_t n) {
  if (n == 2) {
    return true;
  }
  if (n == 1 || (n & 1) == 0) {
    return false;
  }

  uintmax_t d = n - 1;
  while ((d & 1) == 0) {
    d >>= 1;
  }

  uintmax_t a, t, y;
  for (int i = 0; i < 20; i++) {
    a = random(1, n-1);
    t = d;
    y = pow(a, t, n);
    while (t != n-1 && y != 1 && y != n-1) {
      y = (y * y) % n;
      t <<= 1;
    }
    if (y != n-1 && (t & 1) == 0) {
      return false;
    }
  }
  return true;
}

uintmax_t pow(uintmax_t base, uintmax_t power, const uintmax_t mod) {
  uintmax_t result = 1;
  while (power > 0) {
    if ((power & 1) == 1) {
      result = (result * base) % mod;
    }
    base = (base * base) % mod;
    power >>= 1;
  }
  return result;
}

写真か動画取ればよかった。