Python Forum
Divide a number by numbers in a list.
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Divide a number by numbers in a list.
#1
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.
Error:
Traceback (most recent call last): File "python", line 7, in <module> TypeError: int() argument must be a string, a bytes-like object or a number, not 'list'
This is my code
primes = [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?
Reply
#2
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:.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#3
(Sep-14-2018, 01:56 PM)ichabod801 Wrote: 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:.

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 :)
Reply
#4
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.
Craig "Ichabod" O'Brien - xenomind.com
I wish you happiness.
Recommended Tutorials: BBCode, functions, classes, text adventures
Reply
#5
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.
Yoriz write Feb-10-2022, 04:30 PM:
Please post all code, output and errors (in their entirety) between their respective tags. Refer to BBCode help topic on how to post. Use the "Preview Post" button to make sure the code is presented as you expect before hitting the "Post Reply/Thread" button.
Reply
#6
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)
Output:
n = 100 Modulo sum = 1060 count = 1133 time = 0.00000 Optimized Mod sum = 1060 count = 136 time = 0.00000 Eratosthenes sum = 1060 count = 185 time = 0.00000 n = 1000 Modulo sum = 76127 count = 78022 time = 0.00698 Optimized Mod sum = 76127 count = 2850 time = 0.00000 Eratosthenes sum = 76127 count = 3349 time = 0.00000 n = 100000 Modulo sum = 454396537 count = 455189150 time = 43.78123 Optimized Mod sum = 454396537 count = 1395441 time = 0.12371 Eratosthenes sum = 454396537 count = 1445440 time = 0.01496
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))
Output:
n = 2000000 Optimized Mod sum = 142913828922 time = 4.23710 Eratosthenes sum = 142913828922 time = 0.35306
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.
Reply
#7
@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:
Output:
n = 100 Modulo sum = 1060 count = 1133 time = 0.00014 Optimized mod sum = 1060 count = 136 time = 0.00005 Eratosthenes sum = 1060 count = 94 time = 0.00002 Gribouillis sum = 1060 count = 129 time = 0.00008 n = 1000 Modulo sum = 76127 count = 78022 time = 0.00776 Optimized mod sum = 76127 count = 2850 time = 0.00041 Eratosthenes sum = 76127 count = 1200 time = 0.00019 Gribouillis sum = 76127 count = 1593 time = 0.00099 n = 10000 Modulo sum = 5736396 count = 5775223 time = 0.49709 Optimized mod sum = 5736396 count = 60957 time = 0.00593 Eratosthenes sum = 5736396 count = 13833 time = 0.00159 Gribouillis sum = 5736396 count = 18222 time = 0.01214 n = 100000 Modulo sum = 454396537 count = 455189150 time = 40.08849 Optimized mod sum = 454396537 count = 1395441 time = 0.12196 Eratosthenes sum = 454396537 count = 151854 time = 0.01847 Gribouillis sum = 454396537 count = 202674 time = 0.16963
Reply
#8
Those results make more sense. Should have reset the count in timeit. Duplicating code is error prone. Another important lesson!
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  How do I calculate a ratio from 2 numbers and return an equivalent list of about 1000 Pleiades 8 15,436 Jan-05-2024, 08:30 PM
Last Post: sgrey
  Delete strings from a list to create a new only number list Dvdscot 8 1,466 May-01-2023, 09:06 PM
Last Post: deanhystad
  find random numbers that are = to the first 2 number of a list. Frankduc 23 3,012 Apr-05-2023, 07:36 PM
Last Post: Frankduc
  List of random numbers astral_travel 17 2,531 Dec-02-2022, 10:37 PM
Last Post: deanhystad
  Remove numbers from a list menator01 4 1,251 Nov-13-2022, 01:27 AM
Last Post: menator01
  [split] why can't i create a list of numbers (ints) with random.randrange() astral_travel 7 1,428 Oct-23-2022, 11:13 PM
Last Post: Pedroski55
  TypeError: float() argument must be a string or a number, not 'list' Anldra12 2 4,757 Jul-01-2022, 01:23 PM
Last Post: deanhystad
  Split a number to list and list sum must be number sunny9495 5 2,196 Apr-28-2022, 09:32 AM
Last Post: Dexty
  When did the number got included in the list? Frankduc 14 2,980 Feb-03-2022, 03:47 PM
Last Post: Frankduc
  producing numbers out of a list bouraque7878 10 3,619 Nov-12-2021, 09:13 PM
Last Post: jefsummers

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020