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. 

  3. from itertools import count, islice

  4. 

  5. n = int(input())

  6. for i in range(n):

  7.     x, prime = int(input()), True

  8.     sq = int(x**0.5)-1

  9.     if x<2: prime = False

  10.     else:

  11.         for num in islice(count(2), sq):

  12.             if not x%num:

  13.                 prime = False

  14.     print("Prime") if prime else print("Not prime")
download android app