本题使用素数筛或者标记优化都可以。标记优化指计算过的素数打上标记，不再重复计算。为了卡暴力，询问次数可以达到1e8或者1e7左右，属于比较大的输入量，建议scanf。