Geek asks and answers

Search for numbers from a to b not divisible by x by y

This is a problem that I have been thinking about for a long time.

What is the fastest way to find all numbers from a to b that are not divisible by any number from x to y?

Consider this:

I want to find all numbers from 1 to 10 that are not divisible by 2-5. This process will become extremely slow if I use a linear approach; Like this:

result = []
a = 1
b = 10
x = 2
y = 5
for i in range(a,b):
    t = False
    for j in range(x,y):
        if i%j==0:
            t = True
            break
    if t is False:
        result.append(i)
return result

Does anyone know of any other ways to do this with shorter calculation time than a linear solution?

If not, can anyone see how this can be done faster, because at this moment I'm empty ...

Regards, John

[EDIT]

Number range from 0 to> 1, e + 100

This is true for a, b, x and y

+5
source share
2 answers

- , 2, 2; . , 2, 3, 5 - 4, , 4, 2. , , , , .

set: , , . , - .

, , set (, , 1 10) .

: , , , , . , : set [a, b], set, . , , ( [3, 6]), 3 - 6. , [3, 4, 5], .

Edit2: , , :

def find_non_factors():
    a = 1
    b = 1000000
    x = 200
    y = 1000

    z = [True for p in range(x, y+1)]
    for k, i in enumerate(z):
        if i:
            k += x
            n = 2
            while n * k < y + 1:
                z[(n*k) - x] = False
                n += 1

    k = {p for p in range(a, b+1)}

    for p, v in enumerate(z):
        if v:
            t = p + x
            n = 1
            while n * t < (b + 1):
                if (n * t) in k:
                    k.remove(n * t)
                n += 1

    return k

. 1 . 2 .

+4

: . , , , , , , , . , .

x-y a-b:

, x, x + 1, x + 2... y. , 2, 3, 4, 5 60, 120.

booleans - false , x-y , true.

a-b, modulo arraylength, , else, , .

, x y, . - 2, 3, 4, 5, 4 2 * 2 2, , 30. - 3, 4, 5, 6 4 2 * 2 6 3 * 2 - 6 - 3, , 4 , . LCM 3 * 2 * 2 * 5 = 60. ab, , , .

, , - , , - , . , , , .

+3

More articles:


All Articles