What is the best algorithm to solve this puzzle?

So, I came across this question:

How many numbers exist from 1 to 1000, which are not divisible by the numbers 2, 3 and 5?

It seems pretty easy at first, so I wrote a quick python program to solve it:

count = 0
for number in range(1,1000):
    if number % 2 != 0 and number % 3 != 0 and number % 5 != 0:
        count += 1
print(count)

I got the correct answer (266), but I thought that it was a lot to do if I wanted to check more than just 3 values. I also wanted to make a mathematical decision, so I came across this:

1000 - ((1000/2 +1000/3 +1000/5) -(1000/2x3 +1000/2x5 + 1000/3x5)+ (1000/2x3x5)) = 1000-((500+333+200) - (166 +100 + 66) + 33) = 1000- 734 = 266

I thought this was a good approach, so I implemented it in code:

def foo(ln = 1000), numbers = [2,3,5]:
    div = 0
    muldiv = 0
    totdiv = 1


    for n in numbers:
        div += ln/n
    for i in numbers:
        for n in range(numbers.index(i)+1, len(numbers)):
            muldiv += ln/(i * numbers[n])

    for n in numbers:
        totdiv *= n

    answer = ln - (div - muldiv + ln/totdiv)
    print("answer is ", math.floor(answer))

Now I'm sure I mixed up somewhere in my second function, because it doesn't seem to work for more numbers. For example, if I tried to find

How many numbers exist from 1 to 1000, which are not divisible by the numbers 2, 3, 5 and 7?

228 foo(numbers = [2,3,5,7]) 300... , 228 , , , , ? ?

+6
8

, :

, 1 N (), k, :

(/).

, , 3 , 333.

, 2, 3 5; , . : , 15 3 5.

, :

, 2, 3 5, ,

  • , 2
  • , 3
  • , 5
  • , 2 3
  • , 2 5
  • , 3 5
  • , 2, 3 5.

, , :

def n_div(N,k):
    return N//k

def n_div235(N):
    return n_div(N,2)+n_div(N,3)+n_div(N,5)-n_div(N,2*3)-n_div(N,2*5)-n_div(N,3*5)+n_div(N,2*3*5)

def not_div235(N):
    return N-n_div235(N)

, :

>>> not_div235(1000)
266

N , -:

:

import itertools
from functools import reduce
import operator

def gcd(a, b):
    while b:      
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def lcm_list(ks):
    res = 1
    for k in ks:
        res = lcm(res,k)
    return res

def n_div_gen(N,ks):
    nk = len(ks)
    sum = 0
    factor = 1
    for i in range(1,nk+1):
        subsum = 0
        for comb in itertools.combinations(ks,i):
            subsum += n_div(N,lcm_list(comb))
        sum += factor * subsum
        factor = -factor
    return sum

def not_div_gen(N,ks):
    return N-n_div_gen(N,ks)

N , , , 3, 5 7 1 1 000 000 000:

>>> not_div_gen(1000000000,[3,5,7])
457142857

>>> sum(i%3!=0 and i%5!=0 and i%7!=0 for i in range(1,1000000001))
457142857

, . , N.

+5

sum all :

def f(r=1000, nums=(2,3,5)):
    return sum(all(x%n for n in nums) for x in range(1, r+1))

, , (False 0 True 1). A nums of (2,3,5,7) 228, , (, , , ).

+1

N, n 1, n 2,..., n t (, -)

  N
  (SUM 1..t ( N, n i))
  (SUM i, j 1..t, < j ( N, n i n j) )
  (SUM i, j, k 1..t, < k ( N, n i n j n k))
  (SUM i, j, k, l 1..t, < k < l ( N, n i n j n k n l))
............
  (SUM i, j, k, l,... q 1..t, < j < l <... < q ( N n i n j n k n l... n q) )

, t .

, , , -, .

3 . .

+1

, . , Willem Van Onsem ( , ), , . .

from itertools import combinations
from functools import reduce

def prod(seq, mul=int.__mul__):
    return reduce(mul, seq, 1)

def count_coprimes(n, divisors):
    total = n
    sign = -1
    for i in range(1, len(divisors) + 1):
        for k in combinations(divisors, i):
            total += n // prod(k) * sign
        sign = -sign
    return total

print(count_coprimes(1000, [2, 3, 5]))

266

FWIW, , "" ( ). - (-1)**i .

def count_coprimes(n, divisors):
    return n + sum(n // prod(k) * (-1)**i
        for i in range(1, len(divisors) + 1)
            for k in combinations(divisors, i))

print(count_coprimes(1000000000, [3, 5, 7]))

457142857

(-1)**i, :

def div(p, q):
    return p // q if q > 0 else -(p // -q)

def count_coprimes(n, divisors):
    return sum(div(n, prod(k))
        for i in range(len(divisors) + 1)
            for k in combinations([-u for u in divisors], i))
+1

, , , , 1 1000, 1 1000:

count = 0
for number in range(1,1001,2):
    if number % 3 != 0 and number % 5 != 0:
        count += 1
print(count)

, .

, if ( , , , modulo 1000):

def foo(lst):
    count = 0
    for number in range(1,1001,lst[0]):
        if not any([number % i == 0 for i in lst[1:]]):
            count += 1
    return count

>>> foo([2,3,5])
266
>>> foo([2,3,5,7])
228
0

, , :

import timeit


def f1(l, h):
    count = 0
    for number in range(l, h):
        if number % 2 != 0 and number % 3 != 0 and number % 5 != 0:
            count += 1

    return count


def f2(l, h):
    return len(filter(lambda x: x % 2 != 0 and x % 3 != 0 and x % 5 != 0, range(l, h)))


def f3(l, h):
    count = 0
    for number in range(l, h):
        if number % 2 == 0:
            continue
        if number % 3 == 0:
            continue
        if number % 5 == 0:
            continue

        count += 1

    return count


def f4(l, h):
    return len([x for x in range(l, h) if x % 2 != 0 and x % 3 != 0 and x % 5 != 0])

a, b, N = 1, 1000, 10000

print timeit.timeit('f1(a,b)', setup='from __main__ import f1, a, b', number=N)
print timeit.timeit('f2(a,b)', setup='from __main__ import f2, a, b', number=N)
print timeit.timeit('f3(a,b)', setup='from __main__ import f3, a, b', number=N)
print timeit.timeit('f4(a,b)', setup='from __main__ import f4, a, b', number=N)

i7-2.6ghz :

0.802361558825
1.46568073638
0.91737188946
0.846404330893

, , / (1,1000) . , (), , , , , .

0
  • n - <0,n> , d[]={2,3,5,0}; -

  • LCM d[]

    - , SoE . 2,3,5 - lcm=30. max(d[]) ... LCM (LCM>=n), n .

  • SoE <0,LCM)

    LCM a[i]=1 i a[i]=0 i.

  • SoE

    a'[i]=a[0]+a[1]+..a[i]

  • count :

    int(n/LCM)*a'[LCM-1] + a'[n%LCM];
    

++:

int non_divisibles(int n,const int *d)  // SoE
    {
    int i,j,cnt,lcm,m,*a;
    for (m=0;d[m];m++); // compute m
    for (cnt=0,i=0;i<m;i++) if (cnt<d[i]) cnt=d[i]; // cnt = max d[] (to speed up LCM)
    // LCM d[]
    a=new int[m]; if (a==NULL) return -1;
    for (i=0;i<m;i++) a[i]=d[i];
    for (lcm=cnt;lcm<=n;lcm+=cnt) // no need to test above `n` even if lcm is bigger
        {
        for (i=0;i<m;i++) for (;a[i]<lcm;) a[i]+=d[i];
        for (i=0;i<m;i++) if (a[i]!=lcm) { i=-1; break; }
        if (i>=0) break;
        }
    delete[] a;
    // SoE <0,LCM)
    a=new int[lcm]; if (a==NULL) return -1;
    for (i=0;i<lcm;i++) a[i]=1;
    for (j=0;d[j];j++)
     for (i=0;i<lcm;i+=d[j])
      a[i]=0;
    // convert to cnt
    for (i=1;i<lcm;i++) a[i]+=a[i-1];
    // compute whole count
    cnt =(n/lcm)*a[lcm-1];
    cnt+=a[n%lcm];
    delete[] a;
    return cnt;
    }

, SoE SoE (max (n, LCM (d[]))) :

n=1000000 d[]={ 2 3 5 7 11 13 17 19 }
171021 [  27.514 ms] naive
171021 [  12.642 ms] SoE
171021 [  25.438 ms] LCM+Soe

n=1000000 d[]={ 2 3 5 7 11 13 17 }
180524 [  26.212 ms] naive
180524 [  11.781 ms] SoE
180524 [   9.807 ms] LCM+Soe

n=1000000 d[]={ 2 3 5 7 11 13 }
191808 [  24.690 ms] naive
191808 [  11.512 ms] SoE
191808 [   0.702 ms] LCM+Soe

n=1000000 d[]={ 2 3 5 }
266666 [  16.468 ms] naive
266666 [   9.744 ms] SoE
266666 [   0.006 ms] LCM+Soe

n= 1000 d[]={ 2 3 5 }
   266 [   0.012 ms] naive
   266 [   0.012 ms] SoE
   266 [   0.001 ms] LCM+Soe

n=1000000 d[]={ 2 3 5 19 23 61 87 10001 }
237662 [  26.493 ms] naive
237662 [  10.180 ms] SoE
237662 [  19.429 ms] LCM+Soe

As you can see, SoE (n) is better if LCM is too large compared to n( d[]contains many primes or large numbers), but a O(n)space is required .

0
source

You can help out as soon as you click on the dividend.

    def test(tocheck):

        count = 0

        for number in range(1, 1000):

            for div in tocheck:
                if not number % div:
                    break
            else:
                #else on a loop means it ran to completion w.o. break
                count += 1

        print("%d not divisible by %s" % (count, tocheck))


    test([2,3,5])
    test([2,3,5,7])

exit:

266 not divisible by [2, 3, 5]
228 not divisible by [2, 3, 5, 7]
0
source

Source: https://habr.com/ru/post/1014413/


All Articles