Divide a number by numbers in a list. - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: General Coding Help (https://python-forum.io/forum-8.html) +--- Thread: Divide a number by numbers in a list. (/thread-12819.html) |
Divide a number by numbers in a list. - Wallen - Sep-14-2018 Hello. Im trying to get the sum of all prime numbers under 2,000,000. In my code Ive tried to divide a number with only prime numbers in order to lower the amounts of iterations. The code, however, wont read my list of prime numbers as an integer and I get this error. This is my codeprimes = [2, 3] sum = 5 test = 5 counter = 0 while counter < 10000: for i in range(1, int(test**0.5)+1, int(primes)): if i > 0: if test % i != 0: primes.append(i) sum += test counter += 2 test += 2 print(sum)How can I make my code read the list as an integer? RE: Divide a number by numbers in a list. - ichabod801 - Sep-14-2018 You can't. I don't understand what you are trying to do there. int(primes) is being given as the step argument to the range function. You can't step through a sequence by multiple distances at the same time.If you want to loop through the primes to test each one against counter, you should just use for prime in primes: .
RE: Divide a number by numbers in a list. - Wallen - Sep-14-2018 (Sep-14-2018, 01:56 PM)ichabod801 Wrote: You can't. I don't understand what you are trying to do there. So the idea is that its ineficiant to divide a nummer, lets say 541, by every odd nummer up to the square root of 541. So I attempted to create a list were new primes are added as the code iterates and then only dividing the next number to be tested with primes from that list. In this way we don’t need to divide by every odd number, 3, 5, 7, 9 ect. And in this way focus on dividing by the primes, 3, 5, 7, 11 ect. So you think I should change for i in range(1, int(test**0.5)+1, int(primes)):With for prime in primes(1, int(test**0.5)+1, prime):English is not my first language so feel free to speak your mind if I’m not clear enough, and I’ll try to explain better :) RE: Divide a number by numbers in a list. - ichabod801 - Sep-14-2018 No, you should change for i in range(1, int(test**0.5)+1, int(primes)):to for prime in primes:You can loop directly through the items in a list this way. So the first time through the loop it will be 2, the second time it will be 3, and the 5, and so on. But you will have other problems. After the test for each prime, you are adding the prime. Say you get to 9. You will check 9 against 2, and find it doesn't divide evenly. Then you will save 9 as a prime and add it to sum, but 9 is not prime. You need to check that all of the primes do not divide evenly in the number you are checking. I would typically do it this way: for counter in range(3, 10000, 2): for prime in primes: if counter % prime == 0: break else: primes.append(counter) total = sum(primes)The first loop goes through the odd numbers (using step = 2) from 3 to 10000. The second loop goes through any primes you've found. The key is the else statement after the inner for loop. Else statements after loops trigger if the loop exits without a break statement. In this case, the break statement happens if a prime factor is found. So the else statement only triggers if no prime factors are found. Then at the end, you use the sum function to total the primes, rather than keeping a running total. RE: Divide a number by numbers in a list. - mishraakash - Feb-10-2022 low = 1 top = 9 sum = 0 for num in range(low, top+1): if num > 1: for i in range(2, num): if (num % i) == 0: break; else: print(num) sum+=num print("Sum :", sum)Can use this program to get sum of prime number between lower value to top value. P.S. Pls make sure IndentationError. Seems the editor code snippt does not respond correctly. RE: Divide a number by numbers in a list. - deanhystad - Feb-12-2022 Your test for prime-ness works, but it is very inefficient. At least in the original post the code only tested if a number was divisible by a prime number using the knowledge that any number > 1 can be represented as a product of prime numbers. Since there are only 148933 prime numbers in the range 2..2000000, this is a huge reduction in the number of divides required to find all the primes. Since division is an expensive operation it is important to reduce the number of divisions. But what if you could do this with zero divides? The Sieve of Eratosthenes tests if a number is a multiple of any other prime. If not, the number is prime. The algorithm generates the list of prime multiples on the fly. See a description of the algorithm here: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. I wrote both algorithms as prime number generators. I added a counter to keep track of how many "costly" operations were performed by each. I also recorded how long it took to generate all the prime numbers in a given range. This is the code: import time def primes_m(n): """Generate prime numbers <= n. Use modulo to test for prime-ness""" global count count = 0 for p in range(2, n+1): for t in range(2, p): count += 1 if p % t == 0: break else: yield p def primes_m_optimize(n): """primes_m with some simple optimizations""" global count count = 0 if n > 1: yield 2 # Only even prime for p in range(3, n+1, 2): # Only test odd numbers count += 1 for t in range(3, int(p**0.5)+1, 2): # Divide by odd numbers up to sqrt(p) count += 1 if p % t == 0: break else: yield p def primes_e(n): """Generate prime numbers <= n using Sieve or Eratosthenes algorithm""" global count if n > 1: yield 2 # Only even prime not_prime = set() for p in range(3, n+1, 2): # Only test odd numbers count += 1 if p not in not_prime: yield p for np in range(3*p, n+1, 2*p): # add odd multiples of np to not_prime not_prime.add(np) count += 1 def timeit(label, func, n): t = time.time() x = sum(func(n)) t = time.time() - t print(f"{label:15} sum = {x:>10} count = {count:>10} time = {t:3.5f}") for n in (100, 1000, 10000, 100000): print("\nn =", n) timeit("Modulo", primes_m, n) timeit("Optimized mod", primes_m_optimize, n) timeit("Eratosthenes", primes_e, n) For small numbers all three algorithms are very quick, but as the value of "n" grows, the number of "costly" operations grows, and grows very quickly for the unoptimized modulo algorithm. I did not time primes_m(2000000), but I did compute count = 1999995000002 and estimate the time = 17, 512 seconds or 4 hours 51 minutes, 52 seconds.The sieve algorithm is the fastest. I thought this would be mostly due to the reducing the number of "costly" operations, but it is slightly less efficient than the optimized modulo algorithm at doing that. The sieve algorithm is 10 times faster than the optimized modulo because set operations are 10 times faster than division. I just had to know the answer. What is the sum of prime numbers <= 2000000? I removed the counting code and this allowed a slight optimization to the sieve algorithm. def primes_e(n): """Generate prime numbers <= n using Sieve or Eratosthenes algorithm""" if n > 1: yield 2 # Only even prime not_prime = set() for p in range(3, n+1, 2): # Only test odd numbers if p not in not_prime: yield p not_prime.update(range(3*p, n+1, 2*p)) I think this is a great lesson on optimization. The optimized modulo algorithm is over 4000 times faster solving the sum of primes under 2000000 than the unoptimized version. This is all due to doing less. The unoptimized version does 4000 times as much work as the optimized version to get the same result. The sieve version is only 10 times faster than the optimized version. It does about the same amount of work, but it does it in a faster way. Doing less is will always beat doing faster. Yet so often you see programmers trying to speed up their programs by using to do the same amount of work faster.
RE: Divide a number by numbers in a list. - Gribouillis - Feb-12-2022 @deanhystad you forgot to write count = 0 in primes_e() . I ran the test, adding my own version (which is an infinite Eratosthene sieve) and here are the results:
RE: Divide a number by numbers in a list. - deanhystad - Feb-12-2022 Those results make more sense. Should have reset the count in timeit. Duplicating code is error prone. Another important lesson! |