# Python: Detect if a number is divisible by any number in a list

I am trying to filter steps such that it only contains numbers from 1 to step_size that aren't divisible by factors of step_size. However, the only way I can get it to work is using a flag like this, which seems to be suboptimal.

(This is part of a larger prime factorizer, which works quite well with this prime_count, even if it is somewhat arbitrary.)

number = 651687138465 # Some integer > 1
preset_primes = [2, 3, 5, 7, 11, 13, 17]
# Actual code of the question starts here
prime_count = min(max(3, 1 + len(str(number)) // 3), 7)  # Arbitrary, but it works well
step_size = math.prod(preset_primes[:prime_count])
steps = [1]  # 1 is always a step, 2-4 never are
for i in range(5, step_size):
flag_append = True
for prime in preset_primes[:prime_count]:
if not i % prime:
flag_append = False
if flag_append:
steps.append(i)

• Python has built-in functions any and all which evaluate iterables of logical values. You can use generator expressions with them, like any(i % prime == 0 for prime in preset_primes) or all(i % prime != 0 for prime in preset_primes). Nov 12, 2023 at 12:29
• (@aghast: discussed in J_H's older answer.) Nov 12, 2023 at 16:14
• This has been done many times before, including here.
– Mast
Nov 12, 2023 at 18:11

# natural log

I'm unhappy with this expression:

prime_count = ... len(str(number)) // 3


Since the length computes log10(), and 3 is roughly 2.718, it seems it would be more honest to write ln(), or math.log(number).

As written it is a little too magical. If we have benchmark results showing how FP is "too slow" in this context, we should at least have a # comment describing those timings or linking to an url.

It's also unclear why we compute min( ... , 7). The magic number should be expressed as len(preset_primes). But there's no need for it anyway, since a "long" slice, e.g. [:9], will simply consume the seven available factors with no complaint.

# early exit

When we clear flag_append = False, we should take the opportunity to break out of the loop.

Or you might choose to rephrase that loop in terms of the any() function. (Close relative of all().)

# numba

In the interest of speed you might want to put this code in a type annotated helper function. Then you could use numba's @njit decorator to run it compiled instead of running it as interpreted bytecode.

• Regarding the first point - math.log(number)/math.log(1000) is identical to log10(x)/3. But it's not quite the same as what is currently done (only for number=10**n), I will check what the performance impact is. Nov 12, 2023 at 1:51
• Oh, I read that and my first thought was it might relate to density of primes, the familiar N / ln(N) expression. So I didn't want the "natural log" aspect obscured. If there's something else going on there, it would be worthwhile to describe it in a # comment, perhaps with URL citation of some relevant math paper.
– J_H
Nov 12, 2023 at 2:01
• It somewhat relates, yes. In this case the following code will check these steps, shifted by a loop using step_size and as such for smaller numbers, creating lots of steps simply isn't worth it, while larger numbers greatly benefit. The len(str(number)) // 3 has been a better choice than other functions I've tested and as such it's there. Actually, int((1 + math.log(number))/(3*math.log(10))) (the 1+ here is required to be equal to len), which I would have assumed to be identical, returns slightly too small values for numbers close to 10**n, is that just math.log() being inaccurate? Nov 12, 2023 at 2:32
• Along with break, mention/demonstrate for …: ‹body› else: ‹after regular termination›. Nov 12, 2023 at 7:48

i is not divisible by a factor of step_size iff gcd(i, step_size) == 1. Otherwise, that gcd is the corresponding factor or a product of multiple factors such that they divide i.

So you can write:

steps = [1]
for i in range(5, step_size):
if math.gcd(i, step_size) == 1:
steps.append(i)


You could, if you wanted, write that as a list comprehension:

steps = [i for i in range(1, step_size) if math.gcd(i, step_size) == 1]


With that caveat that I had to make the range start at 1, so 2..4 are only excluded because the product of small primes that we used includes 2 and 3.

• (Would have upvoted if the question was tagged algorithm - any insights on performance?) Nov 12, 2023 at 16:24