[HackerRank][Python3] Time Complexity: Primality

Problem :

https://www.hackerrank.com/challenges/ctci-big-o/problem

My Solution :

#!/usr/bin/env python3


def primality(n):
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range(5, int(n**0.5)+2, 2):
        if n % i == 0:
            return False
    return True


p = int(input())
for _ in range(p):
    n = int(input())
    result = primality(n)
    print('Prime') if result else print('Not prime')

Comment :

이 문제는 소수 여부를 판별하는 것이고, n 이하의 모든 소수를 구하는 문제는 아래 풀이 참고 요망

2017/05/07 - [프로그래밍] - [Python] 자연수 n 이하의 소수 구하기