SGU 499:Greatest Greatest Common Divisor

Time Limit:1000MS    Memory Limit:262144KB     64bit IO Format:%I64d & %I64u
Submit
Status
Practice
SGU 499
Description
Andrew has just made a breakthrough in sociology: he realized how to predict whether two persons will be good friends
 or not. It turns out that each person has an inner
friendship number (a positive integer). And the
quality of friendship 
between two persons is equal to the greatest common divisor of their friendship number. That means there are
prime 
people (with a prime friendship number) who just can't find a good friend, and Wait, this is irrelevant to this problem. 
You are given a list of friendship numbers for several people. Find the highest possible quality of friendship among all 
pairs of given people.
Input
The first line of the input file contains an integer
n ( ) — the number of people to process. The next
 
n lines contain one integer each, between 1 and (inclusive), the friendship numbers of the given people. 
All given friendship numbers are distinct.
Output
Output one integer — the highest possible quality of friendship. In other words, output the greatest greatest common 
divisor among all pairs of given friendship numbers.
Sample Input

sample input

sample output

4
9
15
25
16

5

//제목: n개수 중 어느 두 개의 수의 공약수를 찾아내는 값이 가장 크다.
/분석: 직접 폭력 매거 시간의 복잡도 O(n^2)는 허용되지 않습니다.제목에서 n개의 수의 범위가 모두 1000000 이내라는 것을 설명하면 하나의 수조로 할 수 있다
데이터가 몇 번씩 나타나는지 표시합니다.최대 데이터 maxnum을 상한선으로 모든 수 for(maxnum->1)의 배수를 매거하기 시작합니다.
의 배수가 두 번 이상 나타나면 최대 공약수를 얻는다.전체 시간 복잡도는 약 10^6*(log(10^6)이다.

#include<stdio.h>
#include<string.h>
using namespace std;
#define maxn 1000005
#define max(p,q) (p>q?p:q)

int num[maxn],a[maxn];
int main()
{
	int n,i,j,k;
	while(~scanf("%d",&n))
	{
		int maxp=1,ans;
		memset(num,0,sizeof(num));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			maxp=max(maxp,a[i]);
			num[a[i]]++;
		}
		int flag=0;
		for(i=maxp;i>=1;i--)
		{
			k=0;
			for(j=i;j<=maxp;j+=i)
			{
				if(num[j])
					k+=num[j];
				if(k>1)
				{
					printf("%d
",i);
					flag=1;
					break;
				}
			}
			if(flag)
				break;
		}
	}
	return 0;
}