I |
Prime Independence |
A set of integers is called prime independent if none of its member is a prime multiple of another member. An integer a is said to be a prime multiple of b if,
a = b × k (where k is a prime [1])
So, 6 is a prime multiple of 2, but 8 is not. And for example, {2, 8, 17} is prime independent but {2, 8, 16} or {3, 6} are not.
Now, given a set of distinct positive integers, calculate the largest prime independent subset.
Input starts with an integer T (≤ 25), denoting the number of test cases.
Each case starts with an integer N (1 ≤ N ≤ 40000) denoting the size of the set. Next line contains N integers separated by a single space. Each of these N integers are distinct and between 1 and 500000 inclusive.
For each case, print the case number and the size of the largest prime independent subset.
Sample Input |
Output for Sample Input |
3 5 2 4 8 16 32 5 2 3 4 6 9 3 1 2 3 |
Case 1: 3 Case 2: 3 Case 3: 2 |
1. An integer is said to be a prime if it's divisible by exactly two distinct integers. First few prime numbers are 2, 3, 5, 7, 11, 13, ...
Problem Setter: Abdullah Al Mahmud, Special Thanks: Jane Alam Jan