• if gcd(a,b) > 1 there share a prime factor

Sieve of eratosthenes

n = 100

sieve = [0]*(n+1)
for i in range(2, n+1):
    if sieve[i] == 0:
        for j in range(i, n+1, i):
            sieve[j] = i

primes = []
for i in range(2, n+1):
    if sieve[i] == i:
        primes.append(i)

print(primes)

Prime factors

n = 12

sieve = [0]*(n+1)
for i in range(2, n+1):
    if sieve[i] == 0:
        for j in range(i, n+1, i):
            sieve[j] = i
            
pfactors = []
val = n
while val > 1:
    prime = sieve[val]
    pfactors.append(prime)
    while val % prime == 0:
        val //= prime

print(pfactors)