问题 D: 素数的个数

问题 D: 素数的个数

时间限制: 1 Sec  内存限制: 128 MB
提交: 373  解决: 117
[状态] [讨论版] [提交] [命题人:]
题目描述

怎么判断一个整数是不是素数,想必大家是一定会的,今天来做个加强版。给定一个整数n,从[1,n]中任选两个数字相乘求出乘积,显然两个数字的组合有n2 个(例如1*n和n*1算两个组合),这意味着有n2个乘积,更加显然的是通过乘积得出的这n2个整数是有很多重复的。你首先需要对整数去重,然后求剩余的整数中有多少个素数。

输入

第一行输入一个t(0<t<=2000),代表测试数据的组数。

之后t行测试数据,每行一个整数n,m(1<=n<=1000000),其含义如题目所述。

输出

对于每组测试数据,输出一个整数答案,每个答案占一行。

样例输入 Copy
2
3
4
样例输出 Copy
2
2
提示

例如第一组数据,在[1,3]中任选两个数字组合的所有情况为(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3)共9种,求其乘积并去除重复数字后就是[1,2,3,4,6,9]共5个数字,其中有2个素数,因此答案就是2。