The running time is not O(n^2)\$ O(n^2) \$. It is O(n log n)\$ O(n \log n) \$. Why?
T(n) = (n - 2 * 2) / 2 + (n - 2 * 3) / 3 + ... + (n - 2 * (n / 2)) / (n / 2) = O(n log n) (it$$ T(n) = O \bigg( { n - 2 · 2 \over 2 } + { n - 2 · 3 \over 3 } + \dotsb + { n - 2 · { n \over 2 } \over { n \over 2 }} \bigg) = O(n \log n). $$ This is very similar to athe sum of a harmonic series). So it is pretty good in terms of timestime complexity.
It is possible to optimize the code a little bit:
divisors_count = [2] * limit
divisors_count[0], divisors_count[1] = 0, 1
min_divisor = 2
max_divisor = len(divisors_count) // 2
for divisor in range(min_divisor, max_divisor + 1):
for multiple in range(divisor * 2, len(divisors_count), divisor):
divisors_count[multiple] += 1
return divisors_count
I changed the loop over the enumerated list to a loop over a range of divisors and removed the if statement inside the loop's body(in. In my opinion, it also makes the logic more clear because we do not need a list itself in the outer loop). It is also sufficient to iterate only up to len(sieve) // 2(otherwise, because otherwise range(number * 2, len(sieve), number) is empty).
I also gave the variables more meaningful names: divisor instead of number and so on to make the code easier to understand(but the initial version is rather clear, too, in my opinion).
But either way, this code shows a good scalability: it runs for about 1.8 - 1.9s1.8–1.9 seconds with my optimizations (and 2.1 - 2.2s, and 2.1–2.2 seconds without them), for limit = 10 ** 6.
The running time is not O(n^2). It is O(n log n). Why?
T(n) = (n - 2 * 2) / 2 + (n - 2 * 3) / 3 + ... + (n - 2 * (n / 2)) / (n / 2) = O(n log n) (it is very similar to a sum of harmonic series). So it is pretty good in terms of times complexity.
It is possible to optimize the code a little bit:
divisors_count = [2] * limit
divisors_count[0], divisors_count[1] = 0, 1
min_divisor = 2
max_divisor = len(divisors_count) // 2
for divisor in range(min_divisor, max_divisor + 1):
for multiple in range(divisor * 2, len(divisors_count), divisor):
divisors_count[multiple] += 1
return divisors_count
I changed the loop over the enumerated list to a loop over a range of divisors and removed the if statement inside the loop's body(in my opinion, it also makes the logic more clear because we do not need a list itself in the outer loop). It is also sufficient to iterate only up to len(sieve) // 2(otherwise range(number * 2, len(sieve), number) is empty).
I also gave the variables more meaningful names: divisor instead of number and so on to make the code easier to understand(but the initial version is rather clear, too, in my opinion).
But either way, this code shows a good scalability: it runs for about 1.8 - 1.9s with my optimizations (and 2.1 - 2.2s without them) for limit = 10 ** 6.
The running time is not \$ O(n^2) \$. It is \$ O(n \log n) \$. Why?
$$ T(n) = O \bigg( { n - 2 · 2 \over 2 } + { n - 2 · 3 \over 3 } + \dotsb + { n - 2 · { n \over 2 } \over { n \over 2 }} \bigg) = O(n \log n). $$ This is very similar to the sum of a harmonic series. So it is pretty good in terms of time complexity.
It is possible to optimize the code a little bit:
divisors_count = [2] * limit
divisors_count[0], divisors_count[1] = 0, 1
min_divisor = 2
max_divisor = len(divisors_count) // 2
for divisor in range(min_divisor, max_divisor + 1):
for multiple in range(divisor * 2, len(divisors_count), divisor):
divisors_count[multiple] += 1
return divisors_count
I changed the loop over the enumerated list to a loop over a range of divisors and removed the if statement inside the loop's body. In my opinion, it also makes the logic more clear because we do not need a list itself in the outer loop. It is also sufficient to iterate only up to len(sieve) // 2, because otherwise range(number * 2, len(sieve), number) is empty.
I also gave the variables more meaningful names: divisor instead of number and so on to make the code easier to understand(but the initial version is rather clear, too, in my opinion).
But either way, this code shows a good scalability: it runs for about 1.8–1.9 seconds with my optimizations, and 2.1–2.2 seconds without them, for limit = 10 ** 6.
The running time is not O(n^2). It is O(n log n). Why?
T(n) = (n - 2 * 2) / 2 + (n - 2 * 3) / 3 + ... + (n - 2 * (n / 2)) / (n / 2) = O(n log n) (it is very similar to a sum of harmonic series). So it is pretty good in terms of times complexity.
It is possible to optimize the code a little bit:
divisors_count = [2] * limit
divisors_count[0], divisors_count[1] = 0, 1
min_divisor = 2
max_divisor = len(divisors_count) // 2
for divisor in range(min_divisor, max_divisor + 1):
for multiple in range(divisor * 2, len(divisors_count), divisor):
divisors_count[multiple] += 1
return divisors_count
I changed the loop over the enumerated list to a loop over a range of divisors and removed the if statement inside the loop's body(in my opinion, it also makes the logic more clear because we do not need a list itself in the outer loop). It is also sufficient to iterate only up to len(sieve) // 2(otherwise range(number * 2, len(sieve), number) is empty).
I also gave the variables more meaningful names: divisor instead of number and so on to make the code easier to understand(but the initial version is rather clear, too, in my opinion).
But either way, this code shows a good scalability: it runs for about 1.8 - 1.9s with my optimizations (and 2.1 - 2.2s without itthem) for limit = 10 ** 6.
The running time is not O(n^2). It is O(n log n). Why?
T(n) = (n - 2 * 2) / 2 + (n - 2 * 3) / 3 + ... + (n - 2 * (n / 2)) / (n / 2) = O(n log n) (it is very similar to a sum of harmonic series). So it is pretty good in terms of times complexity.
It is possible to optimize the code a little bit:
divisors_count = [2] * limit
divisors_count[0], divisors_count[1] = 0, 1
min_divisor = 2
max_divisor = len(divisors_count) // 2
for divisor in range(min_divisor, max_divisor + 1):
for multiple in range(divisor * 2, len(divisors_count), divisor):
divisors_count[multiple] += 1
return divisors_count
I changed the loop over the enumerated list to a loop over a range of divisors and removed the if statement inside the loop's body(in my opinion, it also makes the logic more clear because we do not need a list itself in the outer loop). It is also sufficient to iterate only up to len(sieve) // 2(otherwise range(number * 2, len(sieve), number) is empty).
But either way, this code shows a good scalability: it runs for about 1.8 - 1.9s with my optimizations (and 2.1 - 2.2s without it) for limit = 10 ** 6.
The running time is not O(n^2). It is O(n log n). Why?
T(n) = (n - 2 * 2) / 2 + (n - 2 * 3) / 3 + ... + (n - 2 * (n / 2)) / (n / 2) = O(n log n) (it is very similar to a sum of harmonic series). So it is pretty good in terms of times complexity.
It is possible to optimize the code a little bit:
divisors_count = [2] * limit
divisors_count[0], divisors_count[1] = 0, 1
min_divisor = 2
max_divisor = len(divisors_count) // 2
for divisor in range(min_divisor, max_divisor + 1):
for multiple in range(divisor * 2, len(divisors_count), divisor):
divisors_count[multiple] += 1
return divisors_count
I changed the loop over the enumerated list to a loop over a range of divisors and removed the if statement inside the loop's body(in my opinion, it also makes the logic more clear because we do not need a list itself in the outer loop). It is also sufficient to iterate only up to len(sieve) // 2(otherwise range(number * 2, len(sieve), number) is empty).
I also gave the variables more meaningful names: divisor instead of number and so on to make the code easier to understand(but the initial version is rather clear, too, in my opinion).
But either way, this code shows a good scalability: it runs for about 1.8 - 1.9s with my optimizations (and 2.1 - 2.2s without them) for limit = 10 ** 6.
The running time is not O(n^2). It is O(n log n). Why?
T(n) = (n - 2 * 2) / 2 + (n - 2 * 3) / 3 + ... + (n - 2 * (n / 2)) / (n / 2) = O(n log n) (it is very similar to a sum of harmonic series). So it is pretty good in terms of times complexity.
It is possible to optimize the code a little bit:
divisors_count = [2] * limit
divisors_count[0], divisors_count[1] = 0, 1
min_divisor = 2
max_divisor = len(divisors_count) // 2
for divisor in range(min_divisor, max_divisor + 1):
for multiple in range(divisor * 2, len(divisors_count), divisor):
divisors_count[multiple] += 1
return divisors_count
I changed the loop over the enumerated list to a loop over a range of divisors and removed the if statement inside the loop's body(in my opinion, it also makes the logic more clear because we do not need a list itself in the outer loop). It is also sufficient to iterate only up to len(sieve) // 2(otherwise range(number * 2, len(sieve), number) is empty).
But either way, this code shows a good scalability: it runs for about 1.8 - 1.9s with my optimizations (and 2.1 - 2.2s without it) for limit = 10 ** 6.