if a number is divisible by all the entries of a list then

Question

This came up while attempting Problem 5 of Project Euler, I'm sorry if this is vague or obvious I am new to programming.

Suppose I have a list of integers

v = range(1,n) = [1, ..., n]

What I want to do is this:

if m is divisible by all the entries of v then I want to set

m/v[i] for i starting at 2 and iterating up

then I want to keep repeating this process until I eventually get something which is not divisible by all the entries of v.

Here is a specific example:

let v=[1,2,3,4] and m = 24

m is divisible by 1, 2, 3, and 4, so we divide m by 2 giving us

m=12 which is divisible by 1, 2, 3, and 4 , so we divide by 3

giving us m=4 which is not divisible by 1, 2, 3, and 4. So we stop here.

Is there a way to do this in python using a combination of loops?

Possible duplicate of [Project Euler 5 in Python - How can I optimize my solution?](https://stackoverflow.com/questions/8024911/project-euler-5-in-python-how-can-i-optimize-my-solution) — mrhallak, Jun 03 '17 at 16:29
Find the LCM of the list and perform m/v[i] untill the result is divisible by the LCM value. — Kajal, Jun 03 '17 at 16:35
In your example you say that 12 / 3 = 6, which is incorrect. Please edit your example. — Will Da Silva, Jun 03 '17 at 17:01
Thank you, I made the edit from 6 to 4, also, I'm aware this may be a duplicate (if this same idea was used to solve the problem elsewhere, this is likely not the best way to do it), but I'm trying to postpone looking at other solutions for now. — user135520, Jun 03 '17 at 20:19

Will Da Silva · Answer 1 · 2017-06-03T17:18:41.797

I think this piece of code should do what you're asking for:

v = [1,2,3,4]
m = 24
index = 1
done = False

while not done:
    if all([m % x == 0 for x in v]):
        m = m // v[index]
        if index + 1 == len(v):
            print('Exhausted v')
            done = True
        else:
            index += 1
    else:
        done = True
        print('Not all elements in v evenly divide m')

That said, this is not the best way to go about solving Project Euler problem 5. A more straightforward and faster approach would be:

solved = False
num = 2520
while not solved:
    num += 2520
    if all([num % x == 0 for x in [11, 13, 14, 16, 17, 18, 19, 20]]):
        solved = True
print(num)

In this approach, we known that the answer will be a multiple of 2520, so we increment the value we're checking by that amount. We also know that the only values that need to be checked are in [11, 13, 14, 16, 17, 18, 19, 20], because the number in the range [1,20] that aren't in that list are factors of at least one of the numbers in the list.

Thank you for the alternative solution. :) – user135520 Jun 05 '17 at 20:41 — user135520, Jun 05 '17 at 20:41

score 1 · Answer 2 · answered Jun 03 '17 at 17:16

1

Try this out of size, have a feeling this is what you were asking for:

v = [1,2,3,4]
m = 24

cont = True
c = 1
d = m

while cont:
    d = d/c
    for i in v:
        if d % i != 0:
            cont = False
            result = d
            break
    c+=1

print (d)

Got an output of 4.

answered Jun 03 '17 at 17:16

Polymer

1,108
1
9
17

Thank you, I didn't think to use True/False conditions, that's actually a smoother way to do it. – user135520 Jun 05 '17 at 20:40

Sadiq · Accepted Answer · 2017-06-05T19:01:01.653

1

I think this code will solve your problem:

i=1
while(True):
    w=[x for x in v if (m%x)==0]
    if(w==v):
        m/=v[i]
        i+=1
        continue
    elif(m!=v):
        break

edited Jun 05 '17 at 19:01

answered Jun 03 '17 at 17:57

Sadiq

184
11

1

This is essentially correct, I think you have to move the i =1, to outside the loop otherwise v[i] doesn't iterate the way we want it to. – user135520 Jun 05 '17 at 16:29
Thanks, all the answers here are great but, I think this is what I was trying to do. – user135520 Jun 05 '17 at 20:39

if a number is divisible by all the entries of a list then

3 Answers3