You can use sieve type algorithm. First, sort the list, now if an element occurs only once, mark all its multiples and push back to the answer list. If an element occurs multiple times and has not been marked, mark its multiples but don’t push back to the answer list. Here is my code(although I didn’t submit it).
Overall Complexity : O(M*log(log(M))), where M = 10^6.
Code
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> vec(n);
int i;
for(i=0;i<n;i++)
cin >> vec[i];
sort(vec.begin(), vec.end());
int mark[1000001] = {0};
int j;
vector<int> ans;
for(i=0;i<n;i++)
{
j = i;
while(j < n && vec[j] == vec[i])
j++;
if(j == i + 1)
{
if(!mark[vec[i]])
{
ans.push_back(vec[i]);
int s = vec[i];
while(s < 1000001)
mark[s] = 1, s+=vec[i];
}
}
else
{
if(!mark[vec[i]])
{
int s = vec[i];
while(s < 1000001)
mark[s] = 1, s+=vec[i];
}
}
i = j - 1;
}
if(ans.size() == 0)
cout << -1 << '\n';
else
{
cout << ans.size() << '\n';
for(auto j : ans)
cout << j << " ";
}
}
Yup , I understand , let me tell u another question(which I actually interpret)
suppose we have an array , same as above , we have to select maximum numbers from array such that in selected number for every pair they are not multiples.
for ex : 4 6 9 8
Let’s say we build a graph where i and j are connected if one is multiple of other. Then in this graph we need to find size of maximum independent set which is NP-hard.
nope @sebastian my question is slightly different, we have to select numbers such that the in selected number no two numbers are divisor or multiple of each other.
I think so, @everule1, @carre can you also see this? I am re-stating the problem here:
From an array where A[i] \le 10^6 , chose the maximum size subset such that there exists no pair x, y and x divides y. Example : {2, 4, 6} then answer should be {4, 6}.