ABC300 D問題 AABCC

atcoder.jp

エラトステネスのふるいで素数のリストを作成して、
を 番目の素数 () とします。
をループして、条件を満たすの個数を求めることを考えます。
すなわち の値を固定すれば、の範囲は となります。
この範囲に入るのが素数リストの何番目から何番目かを求めれば、個数が求められます。
このとき、上限の値は素数リストを二分探索することで高速に求めることができます。

コード例 (Julia)

primes = []   # 素数
prime2 = []   # 素数の2乗

function prime_list(N)
  # エラトステネスの篩

  p = trues(N)
  p[1] = false  # 1は素数ではない

  for i = 1:N
    if ! p[i]
      continue
    end

    for j = i*i:i:N
      p[j] = false
    end
  end

  for i = 1:N
    if  p[i]
      push!(primes,i)     # 素数リスト
      push!(prime2,i*i)   # 素数の2乗リスト
    end
  end

end


function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N = readInt()

  prime_list(Int(floor(sqrt(N))))

  M = length(primes)

  ans = 0

  for i = 1:M
    for j = i+1:M-1
      k = j + 1
      if prime2[i] * primes[j] * prime2[k] > N
        break
      end

      klow = j
      khigh = M
      Nk = div(N, prime2[i] * primes[j])

      while khigh - klow > 1
        kc = div( khigh + klow, 2 )
        if prime2[kc] > Nk
          khigh = kc
        else
          klow = kc
        end
      end

      ans += klow - j

    end
  end

  println(ans)

end  # function solve

# main
solve()