#1826. 质因数
质因数
题目描述
定义 表示 分解质因数后得到的质数个数,例如 。
具体的,令 ,其中,是两两不同的质数,则 给定一个数 ,判断是否存在 ,满足 。
输入格式
第一行一个整数 ,表示数据组数。
接下来 行,每行一个正整数 。
输出格式
输出 行,若对于第 组数据给定的 存在 输出一行一个数 ,否则输出一行一个数 。
样例
6
2
3
4
5
12
514
0
0
0
1
0
1
定义f(x) 表示 x 分解质因数后得到的质数个数,例如 f(6)=2,f(12)=3。
具体的,令 x=p1a1p2a2⋯pkakx=p,其中,p1,p2⋯pk是两两不同的质数,则 f(x)=a1+a2⋯+ak 给定一个数 n,判断是否存在 1<m<n,满足 f(m)>f(n)。
第一行一个整数 T,表示数据组数。
接下来 T 行,每行一个正整数 n。
输出 T 行,若对于第 i 组数据给定的 n 存在 1<m<n,f(m)>f(n) 输出一行一个数 1,否则输出一行一个数 0。
6
2
3
4
5
12
514
0
0
0
1
0
1