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

I'm trying to determine whether the prime factors of a given number are different to the primes that I have in a list.

The number has to:

• be dividable with any of the primes in the list

• not have any other prime factors not in the list

Example:

Given my_primes = [2, 3, 5], then n = 14 should return [7]

14 has factors [1, 2, 7, 14]. It can be divided by 2 (which is in list and prime) but also has 7 as a prime factor not in my list so I want to return that. If number has even 1 prime like this it's enough for me so I don't need to check for 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)


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 is a completely different approach needed to do this task?

I should note that I have been learning python for 4-5 months so I might not be aware of any built-in tools that could make this faster.

(@timer is a function that I wrote to check how long it takes to run a function)

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.

• " Usually these are called divisors " oops , my bad there. " Which I hope is a fair re-wording of " yup my bad again. Just run the code and yeah its much more faster thanks for the explanations ! May 27, 2020 at 12:32