Algorithm to determine the prime numbers between 2 and N. What is wrong?

1
n = int(input("Digite N: "))

lista =[]
divisores =[]
for i in range(2, n+1): 

   for j in range(1,n+1):

       if i>=j:
           if i%j ==0:
               divisores.append(j)
               print("divisores",divisores)
               if len(divisores) ==2:

                   lista.append(i)
                   divisores =[]

print("primos",lista)

In the algorithm above, with N = 4, for example, the output is [2, 3, 4], which is wrong! I could not find the error in the program! Any ideas?

    
asked by anonymous 23.03.2018 / 01:35

1 answer

4

The error is in the position where you checked the number of divisors. When checking inside the% loop of j itself, any number that has at least two divisors will be considered as a prime. For example, suppose you are checking whether the i = 6 number is prime (and that j varies from 1 i , to facilitate); it will be seen that 1 is divisor of 6 and therefore will be inserted in divisores ; after, it will be found that 2 is divisor of 6 and will also be inserted in divisores . At this point, the number 6 has two divisors and therefore satisfies the condition len(divisores) == 2 , thus considering as a prime number. So does number 4 in your example.

To fix, you'll need to check the amount of dividers only after you've found them all by checking out the repeat loop:

n = int(input("Digite N: "))

lista =[]
divisores =[]
for i in range(2, n+1): 
    for j in range(1, i+1):
        if i >= j:
            if i % j == 0:
                divisores.append(j)
                print("divisores",divisores)
    if len(divisores) == 2:
        lista.append(i)
    divisores = []

print("primos",lista)

See working at Repl.it

Note that I also restarted the list of divisors out of condition, so that regardless of whether or not the value is prime, the object restarts before the next iteration of the loop.

Further reading

Another way to solve would be to create the function to check if a given number is prime and use it together with a list comprehension :

def is_prime(n):
    divisores = 0
    for i in range(1, n+1):
        if n % i == 0:
            divisores += 1
    return divisores == 2

N = int(input("Digite N: "))

print([n for n in range(1, N+1) if is_prime(n)])

See working at Repl.it

And, using the solution based on the Sieve of Eratosthenes mentioned above, which would probably be the best solution of the cited ones, we would have:

def sieve_of_eratosthene(N):
    A = [True] * (N+1)
    A[0] = A[1] = False
    for value, prime in enumerate(A):
        if prime:
            yield value
            for i in range(value**2, N+1, value):
                A[i] = False

N = int(input("Digite N: "))

print([n for n in sieve_of_eratosthene(N)])

See working at Repl.it

    
23.03.2018 / 02:07