Find the number in a given range so that the gcd of the number with any element of a given list will always be 1

Question

Given a number M and a list A which contains N elements (A1, A2,...) Find the all the numbers k so that: 1=<k=<M which satisfied gcd(Ai, k) is always equal to 1

Here's my code, the only problem for it is that it uses loops in each other, which slow the process if my inputs are big, how can I fix it so that it requires less time?

N, M = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]
from math import gcd
cnt = 0
print(N)
for k in range(1, M+1):
    for i in range(N):
        if gcd(k, A[i]) == 1:
            cnt += 1
            if cnt == N:
                print(k)
    cnt = 0

inputs example: (first line contains N and M, second contains the list A1, A2,...)

3 12
6 1 5

Answer 1

Just another approach using sympy.theory, factorint and Python sets which from the point of view of speed has on my machine no advantage compared to the math.lcm() or the math.gcd() based solutions if applied to small sizes of lists and numbers, but excels at very large size of randomized list:

M    = 12
lstA = (6, 1, 5)
from sympy.ntheory import factorint
lstAfactors = []
for a in lstA:
   lstAfactors += factorint(a)
setA = set(lstAfactors)
for k in range(1, M+1):
    if not (set(factorint(k)) & setA):
        print(k)

The code above implements the idea described in the answer of Yatisi coded by Tom Karzes using math.gcd(), but is using sympy.ntheory factorint() and set() instead of math gcd(). In terms of speed the factorint() solution seems to be fastest on the below tested data:

# ======================================================================
from time   import perf_counter as T
from math   import gcd, lcm
from sympy  import factorint
from random import choice
#M    = 3000
#lstA = 100 * [6, 12, 18, 121, 256, 1024, 361, 2123, 39]
M    = 8000
lstA = [ choice(range(1,8000)) for _ in range(8000) ]

# ----------------------------------------------------------------------
from sympy.ntheory import factorint
lstResults  = []
lstAfactors = []
sT=T()
for a in lstA:
   lstAfactors += factorint(a)
setA = set(lstAfactors)
for k in range(1, M+1):
    if not (set(factorint(k)) & setA):
        lstResults += [k]
print("factorint:", T()-sT)
#print(lstResults)
print("---")

# ----------------------------------------------------------------------
lstResults = []
sT=T()
#l = 1
#for a in lstA:
#    l = (l*a)//gcd(l, a) # can be replaced by: 
l = lcm(*lstA) # least common multiple divisible by all lstA items
# ^-- which runs MAYBE a bit faster than the loop with gcd()
for k in range(1, M+1):
    if gcd(l, k) == 1:
        lstResults += [k]
print("lcm()    :", T()-sT)
#print(lstResults)
print("---")
# ----------------------------------------------------------------------
lstResults = []
sT=T()
l = 1
for a in lstA:
    l = (l*a)//gcd(l, a) # can be replaced by: 
#l = lcm(*lstA) # least common multiple divisible by all lstA items
# ^-- which runs MAYBE a bit faster than the loop with gcd()
for k in range(1, M+1):
    if gcd(l, k) == 1:
        lstResults += [k]
print("gcd()    :", T()-sT)
#print(lstResults)
print("---")
# ----------------------------------------------------------------------
import numpy as np
A = np.array(lstA)
def find_gcd_np(M, A, to_gcd=1):
    vals = np.arange(1, M + 1)
    return vals[np.all(np.gcd(vals, np.array(A)[:, None]) == to_gcd, axis=0)]
sT=T()
lstResults = find_gcd_np(M, A, 1).tolist()
print("numpy    :", T()-sT)
#print(lstResults)
print("---")

printing

factorint: 0.09754624799825251
---
lcm()    : 0.10102138598449528
---
gcd()    : 0.10236155497841537
---
numpy    : 6.923375226906501
---

The timing results change extremely for the second data variant in the code provided above printing:

factorint: 0.021642255946062505
---
lcm()    : 0.0010238440008834004
---
gcd()    : 0.0013772319070994854
---
numpy    : 0.19953695288859308
---

where the factorint based approach is 20x and the numpy based approach 200x times slower than the gcd/lcm based one.

Run the timing test yourself online. It won't run the case of large data, but it can at least demonstrate that the numpy approach is 100x times slower than the gcd one:

factorint: 0.03271647123619914
---
lcm()    : 0.003286922350525856
---
gcd()    : 0.0029655308462679386
---
numpy    : 0.41759901121258736

1 https://ato.pxeger.com/run?1=3VXBitswED0W9BXDGoq16-zaSbtsAzmk0GN6KLmUkAbFkdcismQkZbc-9Et62Uv7Uf2ajiwnNt1Du7ClUIORpXmaefNmLH39Xjeu1Orh4dvBFaObHy--RDB7locURlfgRMUBQFS1Ng5qbopNrg_KcQPMwjKAKubKHnSb7xKQeRVstqnq5mQrWO60EcoFo2Fqh0NnzEstck6iBfqCGUzSNCWRtG6OkyxN4RxW1wlkY3xv_JglMH7tV9LxqwQm136ejSf4-WZNhk46H6suQoxhb3mcJTdpSikU2sAGhIKw7BdhTUgEo2d5BjJcKldybZrHaiDDD9wepLOe9GrdUg5mGxbscraMKfFkmSfrAVOCOQ6RF7PeZ8wosbxNHId4AAte9n3KKNziIqOtOxAFKO0g9pt6Z3sU6qV3NO9gEEIfWWPk1X5N6hZ8dto3PUsAaY_skpIoGPtN9AhHlc7oMyo-4DXULpK-kUj0i4ZRmwqaYnnO6NUV9m8sE2AUIsiZgi0Hw2vJcr6DbTMF4rHY3_G53-9RkjOL7aurSiuoMK6oJYeduBNWbPFr2wCTsg0HwvHKYsxPoxHclyIvwRyUhcX849t3yGorfFtY_3-5EoNjw4DUuoZ7gf-Yp_bb6nX89xQPAsj-oFo-F-oRT6nW3y5WqNXjdn9SpaL_rVSt139Wqu7YUgd_pOPxr2rijxdVXzJjWNOeMZTseAGFULsNkt2oOl4kME_AaT-fHZO_Y9Iet56kgQvIaGs23B2MalErj5EyxsFn75eSPuScrqYJvNeKr1sRQxjsic_CzlLat9Owyx6zy-il01JYF5-0C1k-UepwC3eX8fFS_gk)

Answer 2

Here's a fast version that eliminates the nested loops:

N, M = [int(v) for v in input().split()]
A = [int(v) for v in input().split()]
from math import gcd
print(N)

l = 1
for v in A:
    l = l*v//gcd(l, v)

for k in range(1, M+1):
    if gcd(l, k) == 1:
        print(k)

It works by first taking the LCM, l, of the values in A. It then suffices to check if the GCD of k and l is 1, which means there are no common factors with any of the values in A.

Note: If you're using a newer version of Python than I am (3.9 or later), you can import lcm from math and replace l = l*v//gcd(l, v) with l = lcm(l, v).

Or, as Kelly Bundy pointed out, lcm accepts an arbitrary number of arguments, so the first loop can be replaced with l = lcm(*A) if you're using 3.9 or later.

Answer 3

This is probably more a math question than a programming question, however, here comes my take: Depending on M and A, it might be better to

1. Find the prime divisors of the Ai (have a look at this) and put them in a set.
2. Either remove (sieve) all multiples of these primes from list(range(1,M+1)), which you can do (more) efficiently by smart ordering, or find all primes smaller or equal to M (which could even be pre-computed) that are not divisors of any Ai and compute all multiples up to M.

Explanation: Since gcd(Ai,k)=1 if and only if Ai and k have no common divisors, they also have no prime divisors. Thus, we can first find all prime divisors of the Ai and then make sure our k don't have any of them as divisors, too.

Answer 4

Using numpy with vectorised operations will be a good alternative when your input range M goes up to hundreds and higher and A is stably small (is about as your current A):

import numpy as np

def find_gcd_np(M, A, to_gcd=1):
    vals = np.arange(1, M + 1)
    return vals[np.all(np.gcd(vals, np.array(A)[:, None]) == to_gcd, axis=0)]

---

Usage:

print(find_gcd_np(100, [6, 1, 5], 1))