Sexist hai koi yaha?

0

0 votes
Sieve, Medium, Math
Problem

Shaili likes to go the parties and recently she was invited for the one. Being a sexist person, She likes to group up with the other sexists and make sexist comments on different people.

After reaching to the destination and she found out that there are exactly N people in the party and each one is having some lucky number associated with him/her. She needs to find out total number of sexists present in the party.

She calls a person X sexist if and only if GCD of lucky number of X and lucky number of each of the other people(Except X) is 1. For this she wants your help. Help her to find this as fast as possible to stop her calling you a SEXIST .

Input Format:

First line contains an Integer N, Total number of people present in the party.

Next line contains N Integers Ai where Ai is the lucky number of ith person.

Output Format:

Print a single Integer, Total number of sexists present in the party.

Constraints:

1<=N<=10^6

1<=Ai<=10^6

Sample Input
6
2 3 5 7 11 13
Sample Output
6
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Person 1 is sexist because

gcd(2,3) = 1,

gcd(2,5) = 1,

gcd(2,7) = 1,

gcd(2,11) = 1,

gcd(2,13) = 1.

GCD of 2 with all other persons is 1 therefore Person 1 is sexist

Similarly every other person is sexist so answer is 6.

Editor Image

?