will-you-be-my-friend-pledge-easy

Max feels lonely after shifting to a new locality, as he does not have any friend there. So his parents bought him a new number from the Integers SuperMarket! Every child in the locality has bought a number from the same market.  

He takes the number to go play with other children in the locality. But to his surprise, there is a rule in the locality, two people A and B can only be considered friends if numbers with A and B are not Coprime, i.e they have a common factor other than 1.  

You are given the number that Max bought and the numbers of other children in the locality. Can you find how many friends he can have?   

Input:
First line contains an integer A, the number that Max has.
Second line contains N, the count of children in the locality.
Third line contains N space-separated integers, where  Xi is the integer with the i^th child.  

Output:
Output the maximum number of friends that Max can make.  

Constraints:
1 ≤ A ≤ 10^3
1 ≤ N ≤ 10^3
1 ≤ Xi  ≤ 10^3

SAMPLE INPUT
6
3
4 7 12

SAMPLE OUTPUT
2

Explanation

Puchi can become friends with First and Third child.

Source: hackerearth | Difficulty: EASY


Solutions:
def Primes(N=1001):
	B=[]
	_Primes=[]
	for x in range(N):
		B.append(0)
	for x in range(2, 1001):
		if B[x]==0:
			_Primes.append(x)
			for y in range(2, (N-1)/x+1):
				B[y*x]=1
	return _Primes			


L=[]

primes=Primes()

for x in range(1001):
	B=[]
	for y in range(1001):
		B.append(0)
	L.append(B)
		
for x in range(2, 1001):
	L[x][x]=1
		
for x in range(1001):
	for y in range(x, 1001):
		if L[x][y]==1:
			for z in primes:
				if (y*z<1001) and (x*z<1001):
					L[x][y*z]=1
					L[x*z][y]=1
					L[x*z][y*z]=1
				elif (x*z<1001):
					L[x*z][y]=1
				elif (y*z<1001):
					L[x][y*z]=1
				else:
					break

for x in range(1001):
	for y in range(1001):
		temp=max(L[x][y], L[y][x])
		L[x][y], L[y][x]= temp, temp
		
A=int(input())
N=int(input())
m=list(map(int, input().split()))
result=0
for n in m:
	result+=L[min(A, n)][max(A, n)]

print(result)	
				
				
		
		
		
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
factors=[]
count=0
a=int(input())
for i in range(2,a/2):
	if a%i==0:
		factors.append(i)
factors.append(a)
n=int(input())
arr=list(map(int,input().split()))
for x in arr:
	for f in factors:
		if x%f==0:
			count+=1
			break;

print(count)


from fractions import gcd
a=eval(input())
count=0
n=eval(input())
l=list(map(int,input().split()))
for i in l:
	if gcd(i,a)!=1:
		count+=1
print(count)
			


from fractions import gcd
A = eval(input())
n = eval(input())
L = list(map(int,input().split()))
count = 0
for i in L:
	if gcd(A,i) != 1:
		count+=1
		
print(count)


import math


MaxNo = int(input())
totalBoysOtherThanMax = int(input())
numbers = input().split(" ")



def isCoprime(a, b):
	upperLimit = min(a,b)
	commonF = 1
	
	for j in range(2, upperLimit + 1):
		if(a % j == 0 and b % j == 0):
			commonF = j
		
	if(commonF != 1):
		return False
	else:
		return True
			

def friendCount(MaxNo, otherNumbers):
	friendCount = 0
	for n in otherNumbers:
		if(isCoprime(MaxNo, int(n)) == False):
			friendCount += 1
	return 	friendCount	
	
	
print(friendCount(MaxNo, numbers))	




from fractions import gcd
a=int(input())
n=int(input())
b=list(map(int,input().split()))
sum=0
for i in b:
	    if gcd(i,a)!=1:
	    	    sum+=1
print(sum)	    	    


	    


def is_comp(a,b):
	for i in range(2, min(a,b)+1):
		if a%i==0 and b%i==0:
			return True
	return False

a = int(input())
f = int(input())
f = list(map(int, input().split()))
c=0
for _ in f:
	if is_comp(a,_):
		c+=1
print(c)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
m = int(input().strip())
_ = input()


ll = input().strip()

mm = []

ll = ll.split(' ')
# print ll

for l1 in ll:
	mm.append(int(l1.strip()))


def f(j, k):
	tmp = j % k
	if tmp == 0:
		return k
	else:
		return f(k, tmp)

count = 0
for m1 in mm:
	if m > m1:
		mt1 = m
		mt2 = m1
	else:
		mt1 = m1
		mt2 = m
	tmp = f(mt1, mt2)
#     print mt1, mt2, tmp
	if tmp > 1:
		count += 1

print(count)



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
from fractions import gcd
a=int(eval(input()))
n=int(eval(input()))
arr=list(map(int,input().split()))
count=0
for i in arr:
	if gcd(i,a)!=1:
		count+=1
print(count) 


from fractions import gcd
a=eval(input())
n=eval(input())
x=list(map(int,input().split()))
count=0
for i in x:
	if gcd(a,i)!=1:
		count+=1
print(count)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def coprime(a,b):
	test =0
	
	for x in range(2,a+1):
	
		if(a%x==0 and b%x==0):
			test=1
			break
	if(test==1):
		return 1
	else:
		return 0
	return 0
y = eval(input())
z = eval(input())
arr = list(map(int, input().split(' ')))
counter =0
for x in arr:
	if(y>x):
		f = coprime(x,y)
	else:
		f = coprime(y,x)
	if(f==1):
		counter=counter+1
print(counter)
	

	


from fractions import gcd
m = eval(input())
t = eval(input())
a = list(map(int, input().split()))
x = 0
for num in range(len(a)):
	if gcd(m, a[num]) != 1:
	    x +=1  
    
print(x)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
m = int(input().strip())
_ = input()


ll = input().strip()

mm = []

ll = ll.split(' ')
# print ll

for l1 in ll:
	mm.append(int(l1.strip()))


def f(j, k):
	tmp = j % k
	if tmp == 0:
		return k
	else:
		return f(k, tmp)

count = 0
for m1 in mm:
	if m > m1:
		mt1 = m
		mt2 = m1
	else:
		mt1 = m1
		mt2 = m
	tmp = f(mt1, mt2)
#     print mt1, mt2, tmp
	if tmp > 1:
		count += 1

print(count)


def gcd(a,b):
	if b==0:
		return a
	return gcd(b,a%b)
	
n=eval(input())
x=eval(input())
a=list(map(int,input().split()))
count=0
for i in a:
	if gcd(i,n)>1:
		count+=1
print(count)


a=int(input())
n=int(input())

x=list(map(int,input().split()))

count=0

for i in x:
	flag=False
	m=min(a,i)
	for j in range(2,m+1):
		if i%j==0 and a%j==0:
			flag=True
			break
	if flag:
		count+=1
print(count)



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def hcf(a,b):
	if(b==0):
		return a;
	else:
		return hcf(b,a%b)

a = int(input())
n = int(input())
numbers = input().split(' ')
friends = 0
for i in numbers:
	if a>int(i):
	    gcd = hcf(a,int(i))
	else:
		gcd = hcf(int(i),a)
	if gcd>1:
		friends += 1
print(friends)	


a = int(input())
count = 0
if 1 <= a <= 1000:
	n = int(input())
	if 1 <= n <= 1000:
		s = (input()).split(" ")
		s = list(map(int,s))
		for i in s:
			mi = min(a,i)
			ma = max(a,i)
                        for j in range(2,mi+1):
                            if a%j == 0 and  i%j == 0 :
                                count += 1
                                break


print(count)


def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x
	
a = eval(input())
N = eval(input())

x=list(map(int,input().split()))
s =0
for i in x:
	if(gcd(a,i)>1):
		#print a,i,gcd(a,i)
		s+=1
print(s)    


n=int(input())
fn=int(input())
a=list(map(int,input().split()))
ans=0
b=[]
for j in range(2,n/2 +1):
	if n%j==0:
		b.append(j)
for i in a:
	tc=0
	for j in b:
		if i%j==0:
			tc+=1
	if tc!=0:
		ans+=1
print(ans)


a=eval(input())
arr=[]
n=eval(input())
arr=list(map(int,input().strip().split()))
count=0
for i in arr:
	x=a
	while(i):
		x,i=i,x%i
	if x!=1:
		count+=1
print(count)