多倍長整数でなく素因数分解を使うのがふつうでしょうね。これならべき乗も簡単ですし。でも、N = 2000が限界でした。
import scala.testing.Benchmark type Facts = List[(Int,Int)] def pow(fs :Facts, e :Int) = fs.map(x => (x._1, x._2 * e)) def sieve(N :Int) = { val a = Array.range(0, N) for(p <- Iterator.from(2).takeWhile(n => n * n < N).filter(n => a(n) == n); k <- Iterator.range(p * 2, N, p)) a(k) = p a } object Test extends Benchmark { def run() = solve } def solve() = { val a = sieve(N + 1) def div_pow(n :Int, d :Int) :(Int,Int) = if(n % d != 0) (0, n) else { val (e, m) = div_pow(n / d, d) (e + 1, m) } def factorize(n :Int) :List[(Int,Int)] = if(n == 1) Nil else { val p = a(n) val (e, m) = div_pow(n, p) (p, e) :: factorize(m) } val it = Iterator.range(2, N + 1).map(factorize).flatMap( a => Iterator.range(2, N + 1).map(pow(a, _))) println (it.toSet.size) } val N = 2000 println (Test.runBenchmark(5))