[Assignment] Counting numbers not multiples of a0,a1,...,an

Question

You are given M and A=[a0,a1,...,an], all positive integers

You program must return the number N of integers between 1 and M not multiple of any of a0...an

Ex: M=15 A=[2,3]

Ouput : 5 because only 1,5,7,11,13 are not multiples of 2 or 3

Answer 1

Sieve is the first thing that comes to mind.

But did anyone try the idea that the number of integers divisible by 2 or 3 is the number of multiples of 2 plus the number of multiples of 3, minus the number of multiples of 6 (lcm of 2 and 3)?

Edit: Code attached. It should be faster for bigger M.
https://code.sololearn.com/cMpGw4uORN6p/?ref=app

Answer 2

VcC, Louis
Interesting. Doing LCM takes its toll.

My complexity depends on the list A and not so much on the number M. So one can try a pretty large M as long as the list A is not too big.

Also, my method cannot be modified to produce the actual list of non-multiples :(

Answer 3

https://code.sololearn.com/c5l2DuvJBZxU/?ref=app

Answer 4

#python3

M= 15
A = [2, 3]
N = 0
for i in range(1, M+1):
temp = 0
for j in A:
temp += i%j
if not(temp == 0):
print(i, end = ' ')
N += 1
print("N is = {}".format(N) )

Answer 5

"Ouput : 5 because only 1,5,7,11,13 are not multiples of 2 or 3"

I feel you meant to say 2 and 3 right? @VcC
if its 2 or 3 then its
1 2 3 4 5 7 8 9 10 11 13 14 15 N is = 13
I edited my previous code.

for eg : (4 is a multiple of 2) or (but not of 3) == true

Kindly clarify

Answer 6

https://code.sololearn.com/ceFdAAXAXBrS/?ref=app

Answer 7

VcC
I learned that trick from you. That uber fast numpy sieve.
You forgot to tag me when defining the challange.

Answer 8

Kishalaya Saha Good remark. Fast for higher n but not fastest until n=10.000:
https://code.sololearn.com/cQ4Tp2geQaYD/?ref=app

Answer 9

VcC Kishalaya Saha
I added Kishalaya's specific example to the list
1000000, [12, 27, 36, 40, 65]
and then his code knocks the socks off the sieve.
https://code.sololearn.com/c2KV9foPRIU8/?ref=app

Answer 10

On the other hand, my code can't even handle A=range(2, 30) and M=30 😂

Answer 11

https://code.sololearn.com/cMBa4X3nQMJ1/?ref=app

Answer 12

Numpy rulez!
https://code.sololearn.com/c10QUf7WfX7g/?ref=app

Answer 13

Wrong result. You need a "break" after N+=1

Answer 14

After your edit it works. Check here for speed comparisons.

https://code.sololearn.com/copf9UPJ1ec9/?ref=app

Answer 15

Louis You win (yours is the last).
https://code.sololearn.com/copf9UPJ1ec9/?ref=app