Skip to main content
fix negated primailty test
Source Link
pjz
  • 2.3k
  • 12
  • 15

Everything holroy said, about choice of algorithm especially. Also:

  1. Skip numbers more quickly: lower = max(lower, 2) before you enter the loop will not only save you the iterations for negative numbers, but will also let you remove the if num > 1 test that's inside the loop, for savings no matter the input.

  2. Move as much as possible outside the loop: n == 2 is only going to happen once, so do it beforehand to save an 'inside the loop' operation.

  3. You only need to test up to sqrt(num). (but, per above, avoid computing it more than once)

  4. When I went to write my own version of this, I found myself replacing your:

     for i in range(2, num):
         if (num % i) == 0:
             break
     else:
         total += num
         list_of_primes.append(num)
    

    with:

     is_prime = not any(num % i == 0 for i in range(2, num))
     if is_prime:
         total += num
         list_of_primes.append(num)
    

So, using both of those, your loop looks like:

list_of_primes = []

# test 2 beforehand for speed
if lower <= 2 <= upper:
    total += 2
    list_of_primes.append(2)

# no sense looking for primes below 3
range_lower = max(lower, 3)

# the largest factor we need to test is sqrt(num)
max_factor = int(num**0.5)

for num in range(range_lower, upper + 1):
    if not any(num % i == 0 for i in range(2, max_factor)):
        total += num
        list_of_primes.append(num)

Everything holroy said, about choice of algorithm especially. Also:

  1. Skip numbers more quickly: lower = max(lower, 2) before you enter the loop will not only save you the iterations for negative numbers, but will also let you remove the if num > 1 test that's inside the loop, for savings no matter the input.

  2. Move as much as possible outside the loop: n == 2 is only going to happen once, so do it beforehand to save an 'inside the loop' operation.

  3. You only need to test up to sqrt(num). (but, per above, avoid computing it more than once)

  4. When I went to write my own version of this, I found myself replacing your:

     for i in range(2, num):
         if (num % i) == 0:
             break
     else:
         total += num
         list_of_primes.append(num)
    

    with:

     is_prime = any(num % i == 0 for i in range(2, num))
     if is_prime:
         total += num
         list_of_primes.append(num)
    

So, using both of those, your loop looks like:

list_of_primes = []

# test 2 beforehand for speed
if lower <= 2 <= upper:
    total += 2
    list_of_primes.append(2)

# no sense looking for primes below 3
range_lower = max(lower, 3)

# the largest factor we need to test is sqrt(num)
max_factor = int(num**0.5)

for num in range(range_lower, upper + 1):
    if any(num % i == 0 for i in range(2, max_factor)):
        total += num
        list_of_primes.append(num)

Everything holroy said, about choice of algorithm especially. Also:

  1. Skip numbers more quickly: lower = max(lower, 2) before you enter the loop will not only save you the iterations for negative numbers, but will also let you remove the if num > 1 test that's inside the loop, for savings no matter the input.

  2. Move as much as possible outside the loop: n == 2 is only going to happen once, so do it beforehand to save an 'inside the loop' operation.

  3. You only need to test up to sqrt(num). (but, per above, avoid computing it more than once)

  4. When I went to write my own version of this, I found myself replacing your:

     for i in range(2, num):
         if (num % i) == 0:
             break
     else:
         total += num
         list_of_primes.append(num)
    

    with:

     is_prime = not any(num % i == 0 for i in range(2, num))
     if is_prime:
         total += num
         list_of_primes.append(num)
    

So, using both of those, your loop looks like:

list_of_primes = []

# test 2 beforehand for speed
if lower <= 2 <= upper:
    total += 2
    list_of_primes.append(2)

# no sense looking for primes below 3
range_lower = max(lower, 3)

# the largest factor we need to test is sqrt(num)
max_factor = int(num**0.5)

for num in range(range_lower, upper + 1):
    if not any(num % i == 0 for i in range(2, max_factor)):
        total += num
        list_of_primes.append(num)
Source Link
pjz
  • 2.3k
  • 12
  • 15

Everything holroy said, about choice of algorithm especially. Also:

  1. Skip numbers more quickly: lower = max(lower, 2) before you enter the loop will not only save you the iterations for negative numbers, but will also let you remove the if num > 1 test that's inside the loop, for savings no matter the input.

  2. Move as much as possible outside the loop: n == 2 is only going to happen once, so do it beforehand to save an 'inside the loop' operation.

  3. You only need to test up to sqrt(num). (but, per above, avoid computing it more than once)

  4. When I went to write my own version of this, I found myself replacing your:

     for i in range(2, num):
         if (num % i) == 0:
             break
     else:
         total += num
         list_of_primes.append(num)
    

    with:

     is_prime = any(num % i == 0 for i in range(2, num))
     if is_prime:
         total += num
         list_of_primes.append(num)
    

So, using both of those, your loop looks like:

list_of_primes = []

# test 2 beforehand for speed
if lower <= 2 <= upper:
    total += 2
    list_of_primes.append(2)

# no sense looking for primes below 3
range_lower = max(lower, 3)

# the largest factor we need to test is sqrt(num)
max_factor = int(num**0.5)

for num in range(range_lower, upper + 1):
    if any(num % i == 0 for i in range(2, max_factor)):
        total += num
        list_of_primes.append(num)