1

Here is my prime number finding algorithm -- it works great (and very fast) up until the limit is set above 173, then it starts throwing

ValueError: list.remove(x): x not in list

I don't understand why this is when it works absolutely fine up until the limit is 174 or above -- here is my code.

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

    if limit % 6 == 0:
        primes.remove(primes[-1])
    return primes
Robbie Barrat
  • 510
  • 1
  • 6
  • 24
  • Is this algorithm based on some well-known prime-finding methodology? Can you comment your code and/or reference a source that describes how the algorithm works? Sticking a println right before the primes.remove() and printing the primes and i might help you understand what is going wrong. – SPKoder Jan 31 '16 at 15:51
  • 3
    It fails because you arrive at the first number with more than one prime factor. Any minimal amount of debugging should have revealed the problem.. So go do that – M4rtini Jan 31 '16 at 16:07
  • Thanks M4rtini -- I just fixed it – Robbie Barrat Jan 31 '16 at 16:28
  • @RobbieBarrat Good, you can then post an answer yourself and accept that http://stackoverflow.com/help/self-answer – M4rtini Jan 31 '16 at 16:29
  • 1
    @SPKoder the algorithm is based on the statement that all prime numbers are of the form of 6k+1or 6k-1. Which is widely used to check if the number is prime. But not all results 6k+1 or 6k-1 are prime number, for example: 6*4+1 = 25 (5*5). So the author uses 6k+1 formula to generate the list of prime candidates and then remove numbers of the type x*x. – teamnorge Feb 01 '16 at 02:04

1 Answers1

0

Here ya go - You don't want to have the print in there, thats just to show what's going on.

def primefinder(limit):
    primes = [2, 3]
    for i in range(4, limit):
        if (prime(i)):
            primes.append(i)
            print (i)

    return primes

def prime(number):
    oldnum = number
    factor = 1
    while number > 1:
        factor += 1
        if number % factor == 0:
            if 1 < factor < oldnum:
                return False
            number //= factor
    return True

primefinder(200000)
devtech
  • 325
  • 1
  • 12
iSkore
  • 7,394
  • 3
  • 34
  • 59
  • If all you're gonna do is give a working, although horribly slow, prime finder. You might as well just link to any of the numerous prime finder questions already answered. http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n – M4rtini Jan 31 '16 at 16:23
  • For limit 100k. This runs in about 1,5 minutes. OP code runs in 3 seconds (with the minor fix needed). Pure python answer in linked post runs in under 5ms – M4rtini Jan 31 '16 at 16:25
  • As the comment above said; this isn't even the same algorithm -- it doesn't work anything like my program. I know I did a pretty horrible job of explaining how it worked (I actually didn't at all), but this doesn't even attempt to use the same method. – Robbie Barrat Jan 31 '16 at 16:26
  • Yes that would help haha, please explain why and how you need it – iSkore Jan 31 '16 at 16:46