Problem 204

ハミング数とは5を超える素因数を持たない正整数のことである.
小さい方からいくつか示すと,1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15...がハミング数である.
10^8未満の正整数のうちハミング数は1105個ある.

正整数のうち,nを超える素因数を持たないような数のことをタイプnの一般化ハミング数と呼ぶことにしよう.
よって,上述のハミング数はタイプ5の一般化ハミング数である.

10^9未満の正整数のうち,タイプ100の一般化ハミング数はいくつあるか.

1分30秒.

## list of prime numbers
limit <- 100
slimit <- sqrt(limit)
sieve <- logical(limit)
sieve[1] <- TRUE
sieve[seq(4, limit, 2)] <- TRUE
for(i in seq(3, slimit, 2))
  if(!sieve[i]) sieve[seq(i*2, limit, i)] <- TRUE
plist <- (1:limit)[!sieve]

## count generalised Hamming numbers of type 100
limit <- 1e9
pll <- length(plist)
count <- 1
countham <- function(n = 1, i = 1){
  if(n >= limit) return(0)
  count <<- count + 1
  for(j in i:pll)
    Recall(n*plist[j], j)
  return(0)
}
countham()
count