이 함수를 개선하여 소수를 결정하는 방법은 무엇입니까?

Question

며칠 전에 인터뷰에서이 문제에 대해 질문을 받았으며 그 동안 해결 해 준 문제를 개선하고 싶습니다. 지금까지 이것이 내가 가진 것입니다. 더 효율적으로 만드는 방법을 모릅니다. 처음에는 다음과 같을 것입니다 :

1) i % 2 == 0 라인을 추가하면 시간이 절약됩니까?

2) 파이썬에서 % 연산자의 시간 복잡도는 얼마입니까? %를 사용하지 않고 숫자가 더 빠른 방법으로 나눌 수 있는지 확인하는 방법이 있습니까?

3) d < = math.sqrt (i)는 i의 제곱근을지나 제수를 계산할 때 쓸모가 없다는 사실을 이용합니다. d는 d = i가 될 때까지 잘 나눕니다. 이것이 최적의 단계 수를 제시합니까? i가 홀수라고 주어진이기 때문에이 4 점을 간다) 제가

5 홀수 주어진 있기 때문에

4) I는 D에서 시작 = 3, I 2 대신에 1 씩 증가.

def is_prime(i): 
    if i < 2: 
     return False 
    if i == 2: 
     return True 
    d = 3 
    if i%2 == 0: #skip even numbers 
     return False 
    while d <= math.sqrt(i): 
     if i%d == 0: 
      return False 
     d += 2 
    return True 

Answer 1

) 이론적으로는 아니지만 실제로는 그렇다. O 표기법의 시간 복잡성을 줄이지 않지만 짝수를 고려하지 않기 때문에 실제로는 줄일 수 있습니다. 따라서이 프로그램은 2 배 빨라질 수 있습니다.

2) 주석에 언급 된대로 일반적으로 유용합니다.

3) 물론. sqrt(i)으로 간주하여 시간 복잡도를 O(i)에서 O(sqrt(i))으로 줄였습니다.

4) 질문이 아닙니다. 그러나 사실입니다.

5) 역시 질문이 아닙니다. 그러나 합리적입니다. 확인한대로 i도 적합하지 않습니다.