Dividing a list of numbers in two groups such that numbers in one group don't have any factor common with the numbers in the other group

tl;dr: Use a prime sieve to get a list of primes, use a disjoint set to store and combine groups

Approach

You're on the right track. You can use the Sieve of Erasthones to get a list of prime numbers, and you only need ~O(n log n) time and memory for prime factoring, which isn't that bad.

Let's reframe the second half of the problem a little bit:

• each number in your original list is a node in a graph
• there is an edge between two nodes if the numbers share a common factor

Now your problem is to find two disjoint groups of nodes. Store these groups in a disjoint set.

Example

A slightly shorter version of your example, with elements [2,3,4,5,6]. Let's keep track of each group of nodes in the subsets column, and iterate through the array above.

| iteration | subsets         | subset1 | description                                                                                                             |
|-----------|-----------------|---------|-------------------------------------------------------------------------------------------------------------------------|
| start     | []              | n/a     |                                                                                                                         |
| 1         | []              | {2}     | add a new subset, 2                                                                                                     |
| 2         | [{2}]           | {3}     | 3 shares no common factors with 2, so create a new subset 2                                                             |
| 3         | [{2},{3}]       | {4}     | 4 shares a common factor with 2, but not with 3, so merge it with {2}                                                   |
| 4         | [{2,4},{3}]     | {5}     | 5 shares no common factors with 2,3 or 4, so create a new subset                                                        |
| 5         | [{2,4},{3},{5}] | {6}     | 6 shares a common factor with {2,4}, so merge it into that.  it also shares a common factor with {3}, so merge that too |
| 6         | [{2,4,3,6},{5}] |         | done                                                                                                                    |   

Method

start with a disjoint set with the standard properties make_set, union and find methods as described on Wikipedia.

1. augment it with get_prime_factors that returns a Python set of prime factors of the elements of that subset for space efficiency, only the parent node should contain this property

def get_prime_factors(x):
    return Find(x)._prime_factors

2. modify union to return a reference to the newly created set and to keep track of the prime factors (set intersection)

def union(x, y):
    # use Wikpidia's code
    # ...

    # add this:
    xRoot._prime_factors |= yRoot._prime_factors
    return xRoot

3. define get_subsets(), a way of iterating over the subsets. the naive way is to iterate over the original array and run find on each. the less naive way is to keep track of parents with another set, but this choice doesn't affect the worst-case runtime.

Code

disjoint_set = AugmentedDisjointSet([])
elems = [2,3,6,5,4]

for new_number in elems:
    subset1 = disjoint_set.make_set(new_number)

    for subset2 in disjoint_set.get_subsets():
        if (subset1.get_prime_factors() & subset2.get_prime_factors()): # merge if the subsets share a common factor
            subset1 = disjoint_set.union(subset1, subset2)

# show result. this may give between 1 (all numbers share a common factor) 
# and infinite subsets (all numbers are relatively prime)
# for your example, this will return something like {2,3,4,6,9}, {5}, {7}
# you can group them however you'd like to.
print('result': disjoint_set.get_subsets())  

Analysis

Worst case runs in O(n^2*a(n)) time, where a(n) is the inverse Ackerman function (i.e. very small), if every element is relatively prime, and O(n) space.