StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PODoes this prime function actually work?
text
Body
copied!<p>Since I'm starting to get the hang of Python, I'm starting to test my newly acquired Python skills on some problems on projecteuler.net.</p> <p>Anyways, at some point, I ended up making a function for getting a list of all primes up until a number 'n'.</p> <p>Here's how the function looks atm:</p> <pre><code>def primes(n): """Returns list of all the primes up until the number n.""" # Gather all potential primes in a list. primes = range(2, n + 1) # The first potential prime in the list should be two. assert primes[0] == 2 # The last potential prime in the list should be n. assert primes[-1] == n # 'p' will be the index of the current confirmed prime. p = 0 # As long as 'p' is within the bounds of the list: while p < len(primes): # Set the candidate index 'c' to start right after 'p'. c = p + 1 # As long as 'c' is within the bounds of the list: while c < len(primes): # Check if the candidate is divisible by the prime. if(primes[c] % primes[p] == 0): # If it is, it isn't a prime, and should be removed. primes.pop(c) # Move on to the next candidate and redo the process. c = c + 1 # The next integer in the list should now be a prime, # since it is not divisible by any of the primes before it. # Thus we can move on to the next prime and redo the process. p = p + 1 # The list should now only contain primes, and can thus be returned. return primes </code></pre> <p>It seems to work fine, although one there's one thing that bothers me. While commenting the code, this piece suddenly seemed off:</p> <pre><code># Check if the candidate is divisible by the prime. if(primes[c] % primes[p] == 0): # If it is, it isn't a prime, and should be removed from the list. primes.pop(c) # Move on to the next candidate and redo the process. c += 1 </code></pre> <p>If the candidate IS NOT divisible by the prime we examine the next candidate located at 'c + 1'. No problem with that.</p> <p>However, if the candidate IS divisible by the prime, we first pop it and then examine the next candidate located at 'c + 1'. It struck me that the next candidate, after popping, is not located at 'c + 1', but 'c', since after popping at 'c', the next candidate "falls" into that index.</p> <p>I then thought that the block should look like the following:</p> <pre><code># If the candidate is divisible by the prime: if(primes[c] % primes[p] == 0): # If it is, it isn't a prime, and should be removed from the list. primes.pop(c) # If not: else: # Move on to the next candidate. c += 1 </code></pre> <p>This above block seems more correct to me, but leaves me wondering why the original piece apparently worked just fine.</p> <p><strong>So, here are my questions:</strong></p> <p>After popping a candidate which turned out not be a prime, can we assume, as it is in my original code, that the next candidate is NOT divisible by that same prime?</p> <p>If so, why is that?</p> <p>Would the suggested "safe" code just do unnecessary checks on the candidates which where skipped in the "unsafe" code?</p> <p><strong>PS:</strong></p> <p>I've tried writing the above assumption as an assertion into the 'unsafe' function, and test it with n = 100000. No problems occurred. Here's the modified block:</p> <pre><code># If the candidate is divisible by the prime: if(primes[c] % primes[p] == 0): # If it is, it isn't a prime, and should be removed. primes.pop(c) # If c is still within the bounds of the list: if c < len(primes): # We assume that the new candidate at 'c' is not divisible by the prime. assert primes[c] % primes[p] != 0 # Move on to the next candidate and redo the process. c = c + 1 </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload