Problem 187 - もうカツ丼はいいよな

Problem 187 - Project Euler

合成数とは少なくとも2つの素因数を含む数の事である．例えば，15=3×5，9=3×3，12=2×2×3などである．
30以下の数の中には素因数(異なる必要はない)を2つだけ含むものが10ある(4, 6, 9, 10, 14, 15, 21, 22, 25, 26)．
n < 10 $^8$ の範囲の合成数について，素因数を2つだけ含むものはいくつあるか？

5分くらいかかったけど，~~きっと早くできるのでまた今度直す．~~*1
最初約数の数をカウントしていこうかと思ったけど，1億とかそういう長さのベクトルを使うと膨大なメモリが必要になるのであまり現実的ではない．
100万くらいまでならストレスなく扱えるような気はする．
今回の場合，1億未満という範囲の広さからしてそもそも配列を使うなということなのだろう．
実際，この問題では別に約数の数を全部調べる必要はない．1億未満の素数から重複を許して2つ取り出す組み合わせのうち，1億を超えないものをカウントすればいい．
今回はnextprime()なんか使って1億/2未満の素数を全て求めてしまっているけど，これは必要なく，ある値以下の素数の個数だけ分かればそれで計算はできる．ということで次回やろう．

limit <- 1e8
## Sieve of Eratosthenes
slimit <- sqrt(limit)
sieve <- logical(slimit)
sievelim <- sqrt(slimit)
sieve[1] <- TRUE
sieve[seq(4, slimit, by=2)] <- TRUE
for(i in seq(3, sievelim, by=2)){
  if(!sieve[i]) sieve[seq(i*2, slimit, by=i)] <- TRUE
}
prime <- (1:slimit)[!sieve]

library(gmp)
count <- 0
pl <- length(prime)
pm <- pl - 1
n <- 2
while(n < limit/2){
  count <- count + pl - pm
  if(pm > 0) pm <- pm - 1
  n <- nextprime(n)
  while(pl != 0 && prime[pl] * n > limit) pl <- pl - 1
}
count