12月 21, 2018

CSSの:nth-child()で素数番目を判定する

素数判定という単語を見て、一度でもプログラミングを学んだことがある人ならば知らない人はいないだろう。入門者向けの教材としてよく使われるからだ。素数判定は奥が深く、高速化など実装には様々な手法がある。しかし、CSS は他のプログラミング言語とは違い、思い通りの処理を書くことができない。唯一、:nth-child() という何番目かを指定する疑似クラスは存在する。つまり、愚直に $ 2 $ の倍数、$ 3 $ の倍数…というような試し割りはできるということだ。

エラトステネスのふるい

素数とは、$ 1 $ より大きく、$ 1 $ と自分自身以外に約数を持たない数のことである。簡単にいえば、$ 11 $ の場合は $ 1 $ と $ 11 $ というように約数が $ 2 $ つしかない数をいう。つまり、素数を判定するには $ 2 $ の倍数でない、$ 3 $ の倍数でない…ことを確認できればよい。たとえば、$ 1 $ から $ 9999 $ までの中の素数を判定してみよう。

<ul>
  <li>1</li>
  <li>2</li>
  <li>3</li>
  <li>4</li>
  <li>5</li>
  ...
  <li>9997</li>
  <li>9998</li>
  <li>9999</li>
</ul>

li {
  background-color: #3ab84d;
}
/* 素数以外 */
li:first-child,
li:nth-child(2n+4),
li:nth-child(3n+6),
li:nth-child(4n+8),
li:nth-child(5n+10)
li:nth-child(6n+12),
li:nth-child(7n+14),
...,
li:nth-child(9997n+19994),
li:nth-child(9998n+19996),
li:nth-child(9999n+19998) {
  background-color: #8f8f8f;
}

$ 1 $ から $ 9999 $ の倍数でないことを :nth-child() を使って指定する。:nth-child() の引数に指定する n は $ 0, $ $ 1, $ $ 2, $ $ 3\ldots $ というように $ 0 $ から始まるため、$ an + 2a $（$ a $ は $ 2 $ 以上の整数）と記述する必要がある。CSS のあとに記述したものは上書きされる性質を利用し、素数でないものは灰色にしておく。しかし、このままでは $ 1 $ から $ 9999 $ まですべてを記述しなければならない。そこで、使うのがエラトステネスのふるいというアルゴリズムだ。

エラトステネスのふるいでは、最初に $ 2 $ から $ n $ までの整数を順に並べ、次に残った素数でない数の中で一番小さい数 $ m $ の倍数をふるい落としていく。そのふるい落す操作を $ m $ が $ \sqrt{n} $ に達するまで繰り返し、残ったものが素数となる。

たとえば、$ n = 20 $ の場合を考えてみよう。まず、先頭の $ 2 $ の倍数をふるい落とすと、$$ \{2,\ 3,\ 5,\ 7,\ 9,\ 11,\ 13,\ 15,\ 17,\ 19\} $$ が残る。次に $ 3 $ の倍数をふるい落すと、$$ \{2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19\} $$ となる。次は $ 5 $ の倍数だが、$ \sqrt{20} $ は $4.47…$ のため、$ 5 $ 以上の倍数を考慮する必要はないので、ここで終了となる。以上をふまえると、疑似クラス :nth-child() の数を大幅に削減できることがわかる。

li {
  background-color: #3ab84d;
}
/* 素数以外 */
li:first-child,
li:nth-child(2n+4),
li:nth-child(3n+6),
li:nth-child(5n+10),
li:nth-child(7n+14),
li:nth-child(11n+22),
li:nth-child(13n+26),
li:nth-child(17n+34),
li:nth-child(19n+38),
li:nth-child(23n+46),
li:nth-child(29n+58),
li:nth-child(31n+62),
li:nth-child(37n+74),
li:nth-child(41n+82),
li:nth-child(43n+86),
li:nth-child(47n+94),
li:nth-child(53n+106),
li:nth-child(59n+118),
li:nth-child(61n+122),
li:nth-child(67n+134),
li:nth-child(71n+142),
li:nth-child(73n+146),
li:nth-child(79n+158),
li:nth-child(83n+166),
li:nth-child(89n+178),
li:nth-child(97n+194) {
  background-color: #8f8f8f;
}

$ \sqrt{9999} $ は $ 99.99… $ より、$ 99 $ 以下の素数の倍数だけ疑似クラス :nth-child() を記述すればよい。

/* 素数 */
li:not(:first-child):not(:nth-child(2n+4)):not(:nth-child(3n+6)):not(:nth-child(5n+10)):not(:nth-child(7n+14)):not(:nth-child(11n+22)):not(:nth-child(13n+26)):not(:nth-child(17n+34)):not(:nth-child(19n+38)):not(:nth-child(23n+46)):not(:nth-child(29n+58)):not(:nth-child(31n+62)):not(:nth-child(37n+74)):not(:nth-child(41n+82)):not(:nth-child(43n+86)):not(:nth-child(47n+94)):not(:nth-child(53n+106)):not(:nth-child(59n+118)):not(:nth-child(61n+122)):not(:nth-child(67n+134)):not(:nth-child(71n+142)):not(:nth-child(73n+146)):not(:nth-child(79n+158)):not(:nth-child(83n+166)):not(:nth-child(89n+178)):not(:nth-child(97n+194)) {
  background-color: #3ab84d;
}
/* 素数以外 */
li:first-child,
li:nth-child(2n+4),
li:nth-child(3n+6),
li:nth-child(5n+10),
li:nth-child(7n+14),
li:nth-child(11n+22),
li:nth-child(13n+26),
li:nth-child(17n+34),
li:nth-child(19n+38),
li:nth-child(23n+46),
li:nth-child(29n+58),
li:nth-child(31n+62),
li:nth-child(37n+74),
li:nth-child(41n+82),
li:nth-child(43n+86),
li:nth-child(47n+94),
li:nth-child(53n+106),
li:nth-child(59n+118),
li:nth-child(61n+122),
li:nth-child(67n+134),
li:nth-child(71n+142),
li:nth-child(73n+146),
li:nth-child(79n+158),
li:nth-child(83n+166),
li:nth-child(89n+178),
li:nth-child(97n+194) {
  background-color: #8f8f8f;
}

また、疑似クラス :not() を使うことで素数番目に対して直接指定することもできる。ちなみに、疑似クラス :not() を使う際に、$ a $ でもない、$ b $ でもない、$ c $ でもないというように複数指定する場合は :not(a):not(b):not(c) と続けて記述する必要がある。間違ってもカンマ区切りにしないようにしてほしい。

素数のカウント

素数番目を指定できただけでも満足だが、素数の個数を知りたい場合もあると考えられる。CSS にはカウンターという機能があり、素数の個数を数えることができる。

<ul>
  <li>1</li>
  <li>2</li>
  <li>3</li>
  <li>4</li>
  <li>5</li>
  ...
  <li>9997</li>
  <li>9998</li>
  <li>9999</li>
</ul>
<div class="count"></div>

カウントを表示するための .count を追加する。カウントする要素より後に配置しないと、正しく動作しないので注意が必要だ。

ul {
  counter-reset: nature prime;
}
li {
  counter-increment: nature prime;
}
li:first-child,
li:nth-child(2n+4),
li:nth-child(3n+6),
li:nth-child(5n+10),
li:nth-child(7n+14),
li:nth-child(11n+22),
li:nth-child(13n+26),
li:nth-child(17n+34),
li:nth-child(19n+38),
li:nth-child(23n+46),
li:nth-child(29n+58),
li:nth-child(31n+62),
li:nth-child(37n+74),
li:nth-child(41n+82),
li:nth-child(43n+86),
li:nth-child(47n+94),
li:nth-child(53n+106),
li:nth-child(59n+118),
li:nth-child(61n+122),
li:nth-child(67n+134),
li:nth-child(71n+142),
li:nth-child(73n+146),
li:nth-child(79n+158),
li:nth-child(83n+166),
li:nth-child(89n+178),
li:nth-child(97n+194) {
  counter-increment: nature;
}

ul で counter-reset プロパティを使って、ul の範囲内だけでカウントされるようにする。li では counter-increment プロパティを使って nature（自然数）と prime（素数）をカウントする。そして、素数以外では nature のみカウントされるようにする。これで、素数の個数をカウントすることができたので、表示してみよう。

.count::before {
  content: counter(nature) ' 個中、素数は ' counter(prime) ' 個';
}

.count の疑似要素 ::before の content プロパティで使える counter() 関数を使って表示する。実際に確認できるようにデモを用意した。

https://takamos.ooo/wp-content/uploads/2018/12/css-prime-number.html

デモでは、個数の表示部分が先頭に配置されているが、Flexbox の機能の1つである order プロパティを使って順番を入れ替えている。

Sassで自動生成

奇数番目を指定したい場合はほとんどないと思われるが、ちょっと試してみたいときに手動でセレクタを記述するのは大変である。そこで、以下のような @mixin を用意した。

@mixin eratosthenes($n, $not: false) {
  $search: ();
  $prime: ();
  $n: sqrt($n);
  $limit: sqrt($n);
  
  @for $i from 2 through $n {
    $search: append($search, $i);
  }
  
  @while nth($search, 1) <= $limit {
    $stash: ();
    $first: nth($search, 1);
    $search: list-remove($search, 1);
    $prime: append($prime, $first);
    
    @for $i from 1 through length($search) {
      $num: nth($search, $i);
      
      @if $num % $first != 0 {
        $stash: append($stash, $num);
      }
    }
    
    $search: $stash;
  }
  
  $prime: join($prime, $search);

  $selector: if($not, ('#{&}:not(:first-child)'), ('#{&}:first-child'));

  @for $i from 1 through length($prime) {
    $tmp: nth($prime, $i);
    $selector: if($not, append($selector, ':not(:nth-child(#{$tmp}n+#{$tmp*2}))'), append($selector, '#{&}:nth-child(#{$tmp}n+#{$tmp*2})'));
  }

  $selector: if($not, str-join($selector, ''), str-join($selector, ',\000a'));
  
  @at-root #{$selector} {
    @content;
  }
}

@function sqrt($x) {
  @if $x < 0 {
    @return null;
  }
  
  $y: 1;
  
  @for $i from 1 through 24 {
    $y: $y - ($y * $y - $x) / (2 * $y);
  }
  
  @return $y;
}

@function list-remove($list, $index) {
  $result: ();
  
  @for $i from 1 through length($list) {
    @if $i != $index {
      $result: append($result, nth($list, $i));
    }
  }
  
  @return $result;
}

@function str-join($list, $separator: ',') {
  $string: '';

  @for $i from 1 through length($list) {
    $item: nth($list, $i);
    $string: $string + if($i == 1, '', $separator) + if(length($item) > 1, str-join($item), $item);
  }

  @return $string;
}

実装はエラトステネスのふるいのアルゴリズムを少し変更したもので、CSS では疑似クラス :nth-child() でふるい落とすため、Sass のコンパイル自体は非常に高速だ。

@debug 'a\000a b';

余談だが、この @mixin を作っている途中で気づいたことがある。従来は Sass で複数行の文字列を出力するのは不可能だと思っていたが、Unicode で改行を示す \000a と入力すれば改行されることがわかった。もしかしたら、前から使えたのかもしれない。

li {
  background-color: #3ab84d;
}
li {
  // 素数以外
  @include eratosthenes(9999) {
    background-color: #8f8f8f;
  }
}

使い方は簡単で、引数にいくつまでの範囲で素数を判定したいかを指定する。

li {
  // 素数
  @include eratosthenes(9999, true) {
    background-color: #3ab84d;
  }
}

また、第2引数に true を指定すると、疑似クラス :not() を使って素数のみを指定できるようになる。あまり実用的ではないが、CSS は奥が深いということがわかってもらえたのではないだろうか。