0

Here is my prime finding algorithm, it works a bit like a sieve of Eratosthenes, but starts off with only numbers of the form 6n+/-1 (all primes excluding 2 and 3 are some form of that). My algorithm is able to take out most composite numbers, but when run to find all the primes below 100, 95 is still left in. This is the only composite number that shows up.

def primefinder(limit):
primes = [2, 3]
for i in range(1, (limit / 6 + 1)):
    primes.append(6 * i - 1)
    primes.append(6 * i + 1)

for i in primes:
    if i > 24:
        for x in primes:
            if x <= i ** 0.5:
                if i % x == 0:
                    primes.remove(i)
                    continue
            else:
                break
return primes

When run with a limit of 100, it returns the following list:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 95, 97]

while it should be returning

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

why is it not removing 95?

Mohammed Aouf Zouag
  • 17,042
  • 4
  • 41
  • 67
Robbie Barrat
  • 510
  • 1
  • 6
  • 24
  • 1
    Don't iterate and remove from a list at the same time, see the dupe. – Martijn Pieters Jan 31 '16 at 14:13
  • If i can't iterate and remove at the same time how would i go about doing it? – Robbie Barrat Jan 31 '16 at 14:17
  • EDIT: nevermind -- i've figured it out by simply adding a [:] to the end of the list i'm iterating (which supposedly creates a copy of the list and iterates through that) – Robbie Barrat Jan 31 '16 at 14:33
  • 1
    FWIW, you could use a generator to make the numbers in (2,3,5,7,11,13,....). See `potential_primes()` in [my answer](http://stackoverflow.com/a/26440674/4014959) for a slightly fancier generator that also eliminates multiples of 5. – PM 2Ring Jan 31 '16 at 14:38

0 Answers0