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

CodePudding user response：

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).

CodePudding user response：

Install if not yet installed sympy and try:

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)

CodePudding user response：

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.