Get the list of prime numbers smaller than N

Asked

Viewed 6,752 times

-3

I have an exercise in which I need to enter a number (N) and calculate with Python which are the numbers below N that are primes.

That’s the code I have now.

num == int(input("Insira um número: ")) 

while num < 0: 
    num == int(input("Valor inválido! Insira um número novamente")) 
    n = 1 c = 0 
    while n < num: 
        if n%1 == 0 and n%n == 0

The problem is that technically every number divided by 1 and by itself has as rest zero, what condition I can use to break this?

python

  • Hello Rodrigo, welcome to Stackoverflow in Portuguese, in order to solve your question we need to see the code you are using to solve your problem, it seems that you want the code running without having the effort to search on the subject.

  • 1

    As you check, mathematically, whether a number is prime or not?

  • num == int(input("Enter a number: ")) while num < 0: num == int(input("Invalid value! Enter a number again") n = 1 c = 0 while n < num: if n%1 == 0 and n%n == 0 the problem is that technically every number divided by 1 and by itself has as rest zero, what condition I can use to break this?

6 answers

8

One of the ways to solve this exercise is through Sieve of Eratosthenes. The idea, superficially, is to get the full list of values between 2 and N and remove those that are not primes. The pseudo-code, taken from the above source, is:

 Input: an integer n > 1.

 Let A be an array of Boolean values, indexed by integers 2 to n,
 initially all set to true.

 for i = 2, 3, 4, ..., not exceeding √n:
   if A[i] is true:
     for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:
       A[j] := false.

 Output: all i such that A[i] is true.

In Python, one way to implement it is:

import math

# Input: an integer n > 1.
N = int(input("N: "))

# Let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true.
A = list(range(2, N))

# for i = 2, 3, 4, ..., not exceeding √n:
for i in range(2, int(math.sqrt(N)+1)):

  # if A[i] is true:
  if i in A:

    # for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:
    for j in range(i**2, N, i):

      # A[j] := false.
      if j in A: A.remove(j)

# Output: all i such that A[i] is true.        
print(A)

If we enter with a value of 30 to N, we get the following output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

See working on Ideone or in the Repl.it.

0

To return how many primes there are between 2 and n (optional question 1 of week 7 of the USP Introduction to Computer Science course):

def n_primos(n):
    n_p = 0
    for i in range(2, n):
        if e_primo(i):
            n_p += 1
        i += 1
    return n_p


def e_primo(n):
    f = 1
    div = 0
    while f <= n:
        if n % f == 0:
            div += 1
        f += 1
    if div > 2:
        return False
    else:
        return True


n_primos(6)

0

A different solution:

VLimite = 1000
VPrimos = []
VComposto = []
VLimite = VLimite + 1
for i in range(VLimite):
  if (i + 1) == 1:
    VComposto = VComposto + [i + 1]
  if (i + 1) not in VComposto:
    if (i + 1) != VLimite:
      VPrimos = VPrimos + [i + 1]
      if (i + 1) ** 2 > VLimite:
        i = VLimite;
      else: 
        for j in range(i + 1, VLimite, i + 1):
          VComposto = VComposto + [j]
print(VPrimos)

0


To receive all prime numbers smaller than one 'n' is simple

Follows the code

from math import sqrt
numero = int(input())
aux = 0
aux1 = 0
if numero > 3:
    print(2,'\n',3)      #Coloquei isso aqui, porque  estavam ficando de fora, haha
while numero > 1:
    aux = sqrt(numero)
    aux = int(aux)
    aux1 = 0
    while aux >= 2:
        if numero%aux == 0:
            aux1 += 1
        if aux == 2:
            if aux1 == 0:
                print(numero)
        aux -= 1
    numero -=1

0

# LISTA OS NÚMEROS PRIMOS ATÉ X(=50) UM ABAIXO DO OUTRO
def primos(x):
for i in range(1, x+1):
    div = 0
    for j in range(1, i+1):
        if(i%j == 0):
            div = div + 1
    if (div == 2):
        print(i)
primos(50)

# LISTA OS NÚMEROS PRIMOS ATÉ X(=50) EM LISTA
numeros = []
def lista(x):
    for i in range(1, x+1):
        div = 0
        for j in range(1, i+1):
             if(i%j == 0):
                 div = div + 1
        if (div == 2):
             numeros.append(i)
   print(numeros)
lista(50)

0

Another xD solution: 

#Criei uma função que calcula se o número é primo ou não
def primo(numero):
    primo = True

    if(numero == 1):
        return False

    for i in range(2,numero):
        if(numero%i == 0):
            primo = False

    if (primo == True):
        return True
    else:
        return False
#Fim da Função

n = int(input("Número: "))

#Loop que printa os números primos excluindo N
for i in range(2,n):
    if(primo(i)):
         print(i)

Browser other questions tagged python

You are not signed in. Login or sign up in order to post.