Short Problem Definition:
You will be given two arrays of integers and asked to determine all integers that satisfy the following two conditions:
- The elements of the first array are all factors of the integer being considered
- The integer being considered is a factor of all elements of the second array
time complexity is
space complexity is
This challenge could also be solved using the Greatest Common Divisor. Given that the range of values is only [1,100], it is safe to assume that the naive solution will terminate within the time limit.
#!/bin/python import sys def isValid(a, b, candidate): for a_ele in a: if candidate % a_ele != 0: return False for b_ele in b: if b_ele % candidate != 0: return False return True n,m = raw_input().strip().split(' ') n,m = [int(n),int(m)] a = map(int,raw_input().strip().split(' ')) b = map(int,raw_input().strip().split(' ')) cnt = 0 for candidate in xrange(max(a), min(b)+1): if isValid(a, b, candidate): cnt += 1 print cnt