数字涂色
标题：数字涂色 | 时间限制：1秒 | 内存限制：262144K | 语言限制：不限
疫情过后，希望小学终于又重新开学了，三年二班开学第一天的任务是将后面的黑板报重新制作。黑板上已经写上了N个正整数，同学们需要给这每个数分别上一种颜色。为了让黑板报既美观又有学习意义，老师要求同种颜色的所有数都可以被这种颜色中最小的那个数整除。现在请你帮帮小朋友们，算算最少需要多少种颜色才能给这N个数进行上色。
while True: try: n = input() clo_array = list(map(int, input().split())) clo_array.sort() N = 0 while(len(clo_array) > 1): fisrt_array = clo_array[0] for clo in clo_array[1:]: if(clo % clo_array[0] == 0): clo_array.remove(clo) clo_array.remove(clo_array[0]) N += 1 if(clo_array): print (N+1) else: print (N) except: break
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int n;
cin>>n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin>>arr[i];
}
sort(arr.begin(), arr.end());
vector<bool> vis(n, 0);
int count = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
ans++;
for (int j = i + 1; j < n; j++) {
if (vis[j] == 0 && arr[j] % arr[i] == 0) {
vis[j] = 1;
count++;
if (count == n) {
break;
}
}
}
}
cout<<ans<<endl;
return 0;
}
