fork(1) download
  1. import math
  2.  
  3. # Input: an integer n > 1.
  4. N = int(input("N: "))
  5.  
  6. # Let A be an array of Boolean values, indexed by integers 2 to n, initially all set to true.
  7. A = list(range(2, N))
  8.  
  9. # for i = 2, 3, 4, ..., not exceeding √n:
  10. for i in range(2, int(math.sqrt(N)+1)):
  11.  
  12. # if A[i] is true:
  13. if i in A:
  14.  
  15. # for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n:
  16. for j in range(i**2, N, i):
  17.  
  18. # A[j] := false.
  19. if j in A: A.remove(j)
  20.  
  21. # Output: all i such that A[i] is true.
  22. print(A)
Success #stdin #stdout 0.01s 27720KB
stdin
30
stdout
N: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]