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

Question

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 above algorithm, with N=4, for example, the output is [2, 3, 4], which is wrong! I couldn’t find the error in the program! Any idea?

Answer 1

The error is in the position where you have checked the number of splitters. When checking within the loop itself j, any number that has at least two divisors will be considered as prime. For example, imagine that it is being checked whether the number i = 6 is prime (and that the value of j range from 1 to i, to facilitate); it shall be noted that 1 is divisor 6 and will therefore be inserted in divisores; after, it will be found that 2 is divisor 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, considering, therefore, as a prime number. The same is true with paragraph 4 of your example.

To fix, you will need to check the amount of splitters only after finding 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 on Repl.it}

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

Additional reading

• How to generate 200,000 primes as fast as possible in Python?

Another way to solve would be to create the function to check if a certain number is prime and use it in conjunction with a comprehensilist on:

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 on Repl.it}

And, using the solution based on the above-mentioned Sieve of Eratosthenes, which would probably be the best solution, 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 on Repl.it}

Answer 2

To succeed in this issue you need to implement an algorithm containing two funções.

1. A function to check whether a dado número is cousin;
2. Another function to display numbers that are primos.

to solve this problem you can use the following algorithm...

def exibiprimos():
    """
    Esta função exibi todos os números primos encontrados.
    :return: número primo.
    """
    li = 2
    ls = int(input('Digite o limite superior: '))

    while li <= ls:
        if primo(li) == True:
            print(f'\033[32m{li}', end='')
            print(',' if li < (ls - 1) else '.', end=' ')
        li += 1


def primo(n):
    """
    Esta função verifica se um dado número é ou não primo.
    :param n: número a ser verificado.
    :return: valor booleano.
    """
    i = 1
    cont = 0
    while i <= n:
        if n % i == 0:
            cont += 1
        i += 1
    if cont > 2:
        return False
    else:
        return True


exibiprimos()

See here the functioning of the algorithm.

Note that this algorithm will find todos the números primos who, perhaps, are among 2 and N.