Faster way to check if number has factor of different primes than given list of primes

Question

im trying to get the factor prime number(s) for given number if its different than the primes that i have in a list.

The number have to:

• dividable with any of the primes in the list

• should not have any other factor as primes other than in the list

example:

my_primes = [2, 3, 5]

n = 14 should return [7]

14 has factors [1, 2, 7, 14], can be divided by prime 2 (which is in list and prime) but also have 7 as factor prime and it is not in my list so i want to return that. If number has even 1 prime like this its enough for me so i dont need to check till i find other primes.

The code i have come up with so far:

from rTime import timer


@timer
def solve(n):
    def is_prime(n):
        i = 2
        while i**2 <= n:
            if n % i == 0:
                return False
            i += 1
        return True

    primes = [2, 3, 5]
    listo = []

    if n % 2 != 0 and n % 3 != 0 and n % 5 != 0:
        return False

    for i in range(2, n):
        if n % i == 0 and is_prime(i) and i not in primes:
            listo.append(i)
        if listo:
            break 

    return listo


result = solve(1926576016)
print(result)

so my problem is it takes 22.36 seconds to check if 1926576016 has any primes like that at the moment. Is there anything i can improve in my code to make it faster or whole different approach needed to do this task.

Should note that i have been learning python since 4-5 months so i might not be aware of any build-in tools that makes this faster and its my first question here sorry if i did something wrong !

(@timer is a function that i have write to check how long it takes to run a function)

Answer 1

A note on terminology,

14 has factors [1, 2, 7, 14]

Usually these are called divisors, while the factors of 14 are taken to be only 2 and 7.

The Algorithm

While it is not entirely clear to me what you need the result to be, there is an alternative approach to finding the answer to the following question:

Does the number have any factors that are not in the list?

Which I hope is a fair re-wording of

[the number] should not have any other factor as primes other than in the list

To answer that question, a possible algorithm is:

For each p in primes, as long as n is divisible by p, divide n by p. The "leftover" n at the end is the product of all the factors of the original n that are not in primes.

For example in Python,

def solve(n):
    primes = [2, 3, 5]
    for p in primes:
      while n % p == 0:
        n = n // p
    return n

Now the result will be 1 if the number n only had the primes as factors, or otherwise it will be whatever is left. In the original function, the leftover would also be essentially be factored (but slowly, and only the first factor is returned). An integer factorization algorithm (there are faster options for that than trial division) could be applied as an extra step to recreate that result, but that is not required to answer the question of whether the number has any other factors that were not in the list primes.

This algorithm would not deal very well with a much longer list of primes (say, millions of primes), but it does deal well with cases such as 1926576016 where the lowest prime factor which isn't in primes is high.