remove all elements in a list not relatively prime

Question

I have a list m in python, and I want to remove all the elements in m that are not relatively prime to all previous elements. So if m=[2,3,4] I want the output to be [2,3].

I tried iterating through the values of m, but it doesnt work since the size of m changes and then the index value is out of range.

possible duplicate of [Remove items from a list while iterating in Python](http://stackoverflow.com/questions/1207406/remove-items-from-a-list-while-iterating-in-python) — tzaman, Sep 15 '15 at 15:00

Mazdak · Answer 1 · 2015-09-15T15:30:06.517

7

You can use enumerate and any within a list comprehension and use fractions.gcd function to get the gcd for each pairs :

>>> from fractions import gcd
>>> [j for i,j in enumerate(m) if not any(gcd(j,t)!=1 for t in m[:i])]
[3, 100, 7, 11, 17]

Also as @mgilson mentioned in comment as a more efficient way instead of simple slicing in any you can use itertools.islice function.

edited Sep 15 '15 at 15:30

answered Sep 15 '15 at 15:03

Mazdak

105,000
18
159
188

are you assuming sorted order? – John Coleman Sep 15 '15 at 15:05
It's possible that your `any` clause could be made more efficient by using `itertools.islice` rather than an actual list slice (though you'd have to `timeit` with real data to make any real claims) – mgilson Sep 15 '15 at 15:08
I think this fails for m = [4,15,20,25]. Maybe need `gcd` from the `fractions` module. – John Coleman Sep 15 '15 at 15:09
@Kasramvd but gcd(a,b) > 1 doesn't imply that either a % b or b % a = 0 – John Coleman Sep 15 '15 at 15:12
@mgilson Yeah, I'll add that too! – Mazdak Sep 15 '15 at 15:16
@JohnColeman That would be `or` I changed it and I think this will resolve the OP's need! – Mazdak Sep 15 '15 at 15:19
@Kasramvd The *definition* of relatively prime involves `gcd`. Why try to avoid it? Your examples fail on [4,6]. 6 isn't relatively prime to 4 -- so OP wants [4] but yours yields [4,6] – John Coleman Sep 15 '15 at 15:22
@JohnColeman Yes you are right, I'll update the question.thanks! – Mazdak Sep 15 '15 at 15:26
@Kasramvd -- *Now* your answer is worth an upvote. I always enjoy seeing elegant list comprehensions in Python. – John Coleman Sep 15 '15 at 15:32

remove all elements in a list not relatively prime

1 Answers1