I have an exercise in which I need to enter a number (N) and calculate with Python which are the numbers less than N that are prime.
This is 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 can I use to break this?
To receive all prime numbers smaller than such an 'n' is simple
Follow 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
One way to resolve this exercise is through the Sieve of Eratosthenes . The idea, superficially, is to get the complete list of values between 2 and N and remove those that are not prime. The pseudo-code, taken from the source mentioned above, 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 a value of 30 for N, we get the following output:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]