Please, am just learning some new algorithm and math concepts!
Is there way on how I can improve my algorithm to get the optimal one in terms of computing time?
I mean compute the result for "hard" case, rather than getting the computer to do it
Given a range of non-zero dividend numbers $[A,B]$ such that $1\leq A , B \leq 10^{18}$, and a set of divisors $D = \{x: 1 \leq x \leq 50\}$, I want to find the total number of non-repeating dividends in [A,B] that can be divided by any number in set D.
Example 1 (doesn't take too much time)
The range of dividend numbers [1,10] and the divisors are {2,3,4}
- list of numbers divisible for divisor 2:
2,4,6,8,10 - list of numbers divisible for divisor 3:
3,6,9 - list of numbers divisible for divisor 4:
4,8
So the total number of non-repeat divisible dividends in [1,10] = 7
Example 2 (takes a lot of time)
[A,B] = [79031836253224256, 403892407826392155]
D = {44, 46, 50, 8, 35,41,6,18, 24, 23, 7, 45, 39, 46, 4, 35, 34}
Output: 161802330522861274
1st version of the algorithm in Python
def solution(A,B,D):
a = set()
for i in range(A,B+1):
for j in D:
if i%j == 0:
a.add(i)
# return the count of a
return len(a)
if __name__ == "__main__":
print(solution(1,10,[2,3,4]))