Python Day 25: Running Time and Complexity

A prime is a natural number greater than 1 that has no positive divisors other than 1 and itself. Given a number, n, determine and print whether it's Prime or Not prime.

  1. # Enter your code here. Read input from STDIN. Print output to STDOUT
  2. from itertools import count, islice
  3. n = int(input())
  4. for i in range(n):
  5. x, prime = int(input()), True
  6. sq = int(x**0.5)-1
  7. if x<2: prime = False
  8. else:
  9. for num in islice(count(2), sq):
  10. if not x%num:
  11. prime = False
  12. print("Prime") if prime else print("Not prime")