How for each divisor from one array to find divisors from another array with a remainder of 0?

Question

Python

I'm writing code.
To compile the matrix, I need a condition that will give True if the element from the list a is divided by the next element from the list b completely.
Now I have a primitive code with a head-on solution, but it does not pass in time. Can I somehow get rid of the list in the list?

n = int(input())

lamps = [False]*n

for i in range(n):
    idk = i+1
    for j in range(len(lamps)):
        jd = j+1
        if jd%idk==0:
            lamps[j] = not lamps[j]

For n = 10000 (10^5), the code fails because of the nested loop. How to speed up?

Answer 1

If I understood the task correctly, then it is necessary to calculate for each i
sum_{j=1..n} (i%j?1:0) % 2.
Or - there are n lamps in a row initially not burning. Every first, every second, third, etc. are switched. The question is which lamps are lit at the end.
Expand the condition. Do not switch every 1st, 2nd, etc. lamp, and calculate for each lamp how many times it will be switched (because switching them all one at a time is slow. Do you need to somehow aggregate the calculations)?
The lamp will be switched exactly as many times as there are divisors in its number. In other words, you need to understand whether the number of divisors for each number is even. We recall that any number can be represented as a prime factorization: p1^k1*p2^k2* ... pm^km. You can count the number of divisors - it will be (k1+1)(k2+1)...(km+1), because each prime number can be included in the divisor in the degree from 0 to ki inclusive.
Now, in what case would this number be odd? Only if all ki are even. And this means that the number is a perfect square (all degrees are even. We take the root, divide the degrees in half, we get an integer).
The total answer is to put true in the array for all indexes i*i.