CODEWITHSUNDEEP
python-3.xprimes
arrey
arrey

Reputation: 29

Finding the logical error in my code to get first 50 primes

I'm trying to write my own formula to find a prime number, but it does not completely work and I cannot find the flaw in my logic. Bare in mind I have taken a look around but cannot find an algorithm that I find similar to mine.

My code:

#Challenge 7

prime = []

num = 0

found = False

while found == False:


    if num == 0 or num == 1:
        num+=1

    else:

        for value in range(2, num+1):

            if len(prime) == 50:
                print('Found all')
                found = True
                break

            if num % value == 0:
                num+=1

            else:
                if num not in prime:
                    prime.append(num)
                else:
                    pass


print(prime)

This code works for first few primes (3, 5, 7...) but it also gives incorrect values like 10, and I don't understand why. If someone could explain it to me so that I can understand where the logical mistake is, I'd appreciate it.

Upvotes: 2

Views: 59

Answers (2)

JohEker
JohEker

Reputation: 627

The error comes from this part

if num % value == 0:
    num+=1

else:
    if num not in prime:
        prime.append(num)
    else:
        pass

You assume that the integer is a prime as soon as we find the first occurence of a non-divisor. But the def for primes is that every integer in the interval [2..prime] is a non-divisor. How do we check if any number does not have any divisors?

def isPrime(x):
    for v in range(2, x):
        if (x % v == 0):
            return False;

    return True;

Something like this would work to check if any given number is a prime or not. And since we now have taken the isPrime part out of the main loop, we no longer need a for loop inside the while. Something like this would do

def isPrime(x):
    for v in range(2, x):
        if (x % v == 0):
            return False;

    return True;

prime = [}
num = 2 
found = False

while found == False:

    if len(prime) == 50:
        print("found all")
        found = True
        break

    if(isPrime(num)):
        print(num)
        prime.append(num)
        num+=1

    else:
        num+=1

Upvotes: 2

Kaiser Dandangi
Kaiser Dandangi

Reputation: 230

If you set a breakpoint for when num == 10 you will see the problem clearly.

When you start doing you division check inside of for value in range(2, num + 1): the second number is 3, so num (10) modulo value (3) is 1, which is your test for determining a prime. What your test should be is that it not divisible by any number less than it (less than half is actually sufficient since you check with 2 anyway).

So, consider instead:

    else:
        is_indivisible = True
        # loop through all numbers less than it not including itself
        # (because x % x == 0)
        for value in range(2, num - 1):
            # it is only indivisible if it was previously indivisible
            # And the check is same as before, modulo != 0
            is_indivisible = is_indivisible and (num % value != 0)
            if not is_indivisible:
                break

        # if it is indivisible and it doesn't exist in prime list yet
        if is_indivisible and num not in prime:
            prime.append(num)

        # move on to the next number
        num += 1

Upvotes: 1

Related Questions