链接：https://www.nowcoder.net/acm/contest/71/A
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给定n个正整数，请找出其中有多少个数x满足：在这n个数中存在数y=kx，其中k为大于1的整数

输入描述:


 
第一行输入一个n
接下来一行输入n个正整数ai

输出描述:

输出符合条件个数

 
示例1

输入

5
1 2 3 4 5

输出

2

说明

5个数中1和2符合条件，1是后面每个数的因子，2是4的因子

备注:

1≤n,ai≤1000000
题解：
原本的思路是所有数据for循环一遍并判断是否符合条件，可是时间复杂度太高O（n*n）超时了。
询问了一下大神，他用数组存下数据，然后进行判断相加。还要注意一点，数据可能相等，例如：出现
5
1 2 2 3 4
这里面有两个2，要注意。

 
#include<stdio.h>
#include<string.h>
int a[1000005];
int main()
{
	int t;
//	while(~scanf("%d",&t))
//	{
		scanf("%d",&t);
		int i,n,j,sum=0,max=0;
		memset(a,0,sizeof(a));
		while(t--)
		{
			scanf("%d",&n);
			a[n]++;
			if(n>max)
			max=n;
		}
		for(i=1;i<1000005;i++)
		{
			if(a[i]!=0)
			{
				for(j=i*2;j<=max;j=j+i)
				{
					if(a[j]!=0)
					{
						sum=sum+a[i];
						break;
					}
				}
			}
		}
		printf("%d\n",sum);
//	}
	return  0;
}