Python - Check if numbers in list are factors of a number

Question

Hey,

I have a list of numbers (integers) (say, from 1 to 10).

They're not necessarily consecutive, but they are in ascending order.

I've prompted the user multiple times to enter a choice of the available numbers. When that number is entered, it is removed from the list along with any of its factors that may be there.

I've prevented the user from selecting prime numbers. However, at some point in time, there may be non-prime numbers there, which have no factors remaining.

I'm relatively new to Python, so I'm having trouble implementing:

• Checking if the number selected has no factors remaining (even if it is not prime).

• Checking if only prime numbers remain, or numbers without factors.

I'm thinking of using for statements, but I'm not sure exactly how to implement them. Can anyone offer advice, or code? Thanks in advance...

Answer 1

For the first problem, you could use list comprehensions to build a new list where each element is not the number selected and not a factor of the number selected (see code). Compare this with your original list.

$ python
>>> selected_number = 6
>>> [x for x in range(1,11) if selected_number % x]
[4, 5, 7, 8, 9, 10]

For the second problem, check if each element is prime. If not, check for numbers without factors; for each element, you might mod over the original list and check if it's a list of zeros. I'm sure there's a faster way, though.

Answer 2

If L is a list of non-zero numbers, the list of those which are factors of a number N is:

factors = [x for x in L if N % x == 0]

The list will simply be empty if N has no factors in L, of course.

I'm not sure what you mean by "numbers without factors", unless you mean "primes" (?) -- there have been several SO questions and answers on checking primality in Python, I'd use gmpy.is_prime (from my extension gmpy) but then of course I'm biased;-).

If you mean, "all numbers that have no factors in L", well, there's infinitely many of them, so it's kind of hard to make a list of them all. An unbounded generator for them:

import itertools

def nofactorsinlist(L):
  for i in itertools.count():
    if any(x for x in L if i % x == 0):
      continue
    yield i

Some optimizations would be possible, but this one is really simple and I'm loath to add complicated optimizations without understanding exactly what it is that you're after!-)

Answer 3

To check if there are any factors of the number guess remaining you can use any():

hasfactors = any(guess % n == 0 for n in numbers)

To check if all the remaining numbers are prime, all() can be used. (Since you say you already prevented the user from inputting prime numbers I assume you have some kind of isprime() function):

onlyprimes = all(isprime(n) for n in numbers)