You are given a sequence of integers a1,a2,…,an. You need to paint elements in colors, so that:
For example, it‘s fine to paint elements [40,10,60]in a single color, because they are all divisible by 10. You can use any color an arbitrary amount of times (in particular, it is allowed to use a color only once). The elements painted in one color do not need to be consecutive.
For example, if a=[6,2,3,4,12]then two colors are required: let‘s paint 6, 3 and 12 in the first color (6, 3 and 12 are divisible by 3) and paint 2 and 4 in the second color (2 and 4 are divisible by 2). For example, if a=[10,7,15]then 3 colors are required (we can simply paint each element in an unique color).
The first line contains an integer n (1≤n≤100), where n is the length of the given sequence.
The second line contains n integers a1,a2,…,an (1≤ai≤100). These numbers can contain duplicates.
Print the minimal number of colors to paint all the given numbers in a valid way.
6 10 2 3 5 4 2
3
4 100 100 100 100
1
8 7 6 5 4 3 2 2 3
4
In the first example, one possible way to paint the elements in 3 colors is:
In the second example, you can use one color to paint all the elements.
In the third example, one possible way to paint the elements in 4 colors is:
题意解释：输入n个数，对一个数进行涂色时，被涂色的数的倍数也会被涂色。输出最少涂几次可以涂完所有的数
思路和筛法是一样的，从小的往大的筛，直到筛完为止。
#include <bits/stdc++.h> using namespace std; int a[105]; int main() { int n; cin>>n; for(int i=0;i<n;++i) { int t; cin>>t; a[t]=t; } int ans=0; for(int i=1;i<=100;++i) { if(a[i]) { for(int j=i;j<=100;j+=i) { a[j]=0; } ans++; } } cout<<ans; return 0; }
原文：https://www.cnblogs.com/yoududezongzi/p/11524277.html
