48 lines
631 B
C++
48 lines
631 B
C++
#include<cstdio>
|
|
int n,a[15],len;
|
|
int gcd(int a,int b)
|
|
{return b==0?a:gcd(b,a%b);}
|
|
struct node
|
|
{
|
|
int v;
|
|
node *next;
|
|
node()
|
|
{
|
|
v=-1;
|
|
next=0;
|
|
}
|
|
};
|
|
node* group[15],*p,*t;
|
|
int main()
|
|
{
|
|
scanf("%d",&n);
|
|
int i,j;
|
|
for(i=0;i<n;i++) scanf("%d",a+i);
|
|
len=1;
|
|
group[0]=new node;
|
|
group[0]->v=a[0];
|
|
for(i=1;i<n;i++)
|
|
{
|
|
for(j=0;j<len;j++)
|
|
{
|
|
p=group[j];
|
|
while(p!=0)
|
|
{
|
|
if(gcd(p->v,a[i])>1) goto addr1;
|
|
p=p->next;
|
|
}
|
|
t=new node;
|
|
t->v=a[i];
|
|
t->next=group[j];
|
|
group[j]=t;
|
|
goto allright;
|
|
addr1:;
|
|
}
|
|
group[len]=new node;
|
|
group[len++]->v=a[i];
|
|
allright:;
|
|
}
|
|
printf("%d\n",len);
|
|
return 0;
|
|
}
|