Friend numbers P22662


Statement
 

pdf   zip

html

Let x1, …, xn be a non-empty sequence of natural numbers, all of them strictly larger than 1, and let gcd(x, y) stand as usual for the greatest common divisor of x and y. We say that xi is a friend of xj if and only if at least one of these conditions hold:

  • gcd(xi, xj) > 1;
  • xi is a friend of some xk, and xj is also a friend of xk.

Write a program such that, given a sequence of numbers, computes the size of the largest set of friends in it.

Input

Input consists of several cases. Every case begins with a number n ≥ 1, followed by n different integer numbers, all them between 2 and 100000.

Output

For every case, print the size of the largest set of friends.

Public test cases
  • Input

    4
    21 2 25 14
    3
    5 18 7
    

    Output

    3
    1
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Segon Concurs de Programació de la UPC - Segona Semifinal
    Date
    2004-09-15