$1$과 자기 자신만을 약수 로 가지는 수를 소수 라고 한다.

자연수 $N$에 대해서, $2 \leq m \leq N - 1$인 모든 자연수 $m$에 대하여 $N$을 $m$으로 나눈 나머지가 $0$이 아니라면 (즉, $N$이 $2 \leq m \leq N - 1$인 약수 $m$이 없다면)
$N$은 소수라고 할 수 있다.

방법 1. $N$을 일일이 $2$부터 $N - 1$까지 나눠보기

(입력되는 수가 1보다 큰 자연수라는 보장이 있으면 "if N == 1: return False" 부분은 빼도 좋습니다.)
물론 진짜 $N - 1$까지의 수로 모두 나눠보는것은 비효율적입니다.
$N$이 1조에 가까운 어떤 수라고 가정하면 말 그대로 1조번의 연산이 필요할 수 있습니다. 따라서 조금 더 빠르게 할 수 있는 방법을 생각해야합니다.
어떤 두 소수 $p$, $q$에 대하여 $N = pq$라 한다면, 두 소수중 하나는 필수적으로 $\sqrt{N}$보단 작을 것입니다.
만약 두 소수 $p$, $q$가 $p > \sqrt{N}$, $q > \sqrt{N}$이면 $pq > \sqrt{N} \times \sqrt{N} = N$에서 $pq > N$인데, $N = pq$ 라 했으므로 모순입니다.
따라서 $N$을 $2$부터 $\sqrt{N}$까지만 (정확히는 $\sqrt{N}$를 올림한) 나눠봐도 충분합니다.

방법 2. $N$을 $2$부터 $\lceil \sqrt{N} \rceil$까지만 나눠보기

방법 2보다도 2배 더 빠르게 하는 법이 있습니다.
$2$로만 나누고 나면 짝수로 나눌 필요가 없습니다.
$N$을 $2$로 나눈 나머지가 $1$이었다면 $N$은 홀수이므로, $N$을 다른 짝수로 나눠봐도 어차피 나머지가 $0$이 아니라는 자명한 결과가 나옵니다.
따라서 $2$로만 먼저 나누어보고, 그 다음으로는 홀수로만 계속 나눠봅니다.

방법 3. $N$을 우선 $2$로 나눠보고, $3$부터 $\lceil \sqrt{N} \rceil$ 까지의 홀수로만 나눠보기

방법 3보다 또 1.5배 더 빠르게 하는 방법이 있습니다.
방법 2에서는 짝수를 배제했던 것처럼, 추가적으로 배제할 수 있는 숫자들이 존재합니다.
모든 자연수는 6으로 나눈 나머지가 0, 1, 2, 3, 4, 5 뿐입니다.
$6k + 1 = 1, 7, 13, 19, 25, 31, \cdots$ (나머지 1)
$6k + 2 = 2, 8, 14, 20, 26, 32, \cdots$ (나머지 2)
$6k + 3 = 3, 9, 15, 21, 27, 33, \cdots$ (나머지 3)
$6k + 4 = 4, 10, 16, 22, 28, 34, \cdots$ (나머지 4)
$6k + 5 = 5, 11, 17, 23, 29, 35, \cdots$ (나머지 5)
$6k + 6 = 6, 12, 18, 24, 30, 36, \cdots$ (나머지 6)
방법 3에서 $2$를 제외한 모든 짝수를 날려버렸으니, $6k + 2$, $6k + 4$, $6k + 6$ 꼴의 수를 날려버린 셈입니다.
여기서 $6k+3$꼴의 수들도, $3 \times (2k + 1)$ 꼴로 쓸 수 있으니, $3$을 제외하고 전부 날려버릴 수 있습니다.
$3$으로 나누어봤을 때 나머지가 $0$ 이 아니었는데 $9$, $15$, $21$, $27$...등으로 나누어봐도 어차피 나머지가 $0$이 아닐 것이란걸 알고 있기 때문입니다.

방법 4. $N$을 우선 $2$와 $3$으로 나눠보고, $5$부터 $\lceil \sqrt{N} \rceil$ 까지의 $6k \pm 1$ 유형의 수로만 나눠보기

(이 후의 내용은 빠른 거듭제곱을 구현해야 합니다. 파이썬에서는 파이썬 pow 함수 를 사용해주시면 됩니다.)

방법 5. $N$을 $2$에 대한 페르마 판정법 ("if pow(2, N-1, N) != 1 : return False") 시행 후 일일이 나눠보기

정수론의 성질을 이용하여 소수 대신 합성수 대다수를 아주 빠르게 판단할 수는 있습니다.
페르마의 소정리 에 따라, $p$가 소수이면 $p$와 서로소인 자연수 $a$에 대하여 $a^{p - 1} \equiv 1 \pmod{p}$ 입니다.
정수론 같은건 모르겠다라고 하시는 분들은, 그냥 일일이 나눠보기 직전에 "if pow(2, N-1, N) != 1 : return False"만 넣어보셔도 대다수의 합성수를 빠르게 거른다는 사실을 알 수 있습니다.
물론, Poulet Number , 카마이클 수 같은 일부 이상한 수들은 걸러내지 못하지만, 그래도 기존의 코드와는 비교도 못하게 빨라집니다.
시간복잡도는 최선의 경우 $Ω(\ln N)$ (한방에 소수가 아니라고 판별한 경우), 최악의 경우 $O(\sqrt{N})$ 입니다.

아직도 느리다라고 생각되시는 분들에게 적합한 소수 판별법이 있습니다.
앞에서 이용한 정수론의 성질을 더 이용해서 만드는, 굉장히 빠른 밀러-라빈 소수판별법 도 존재합니다.
구현하는건 약간의 지식이 필요하지만, 더더욱 복잡한 소수 판별법들보단 만들기 쉽고 빠릅니다. (타원곡선 소수 판별법 같은거보다는 훨씬 낫습니다..)
부동소수점 오차때문에 int(N ** 0.5) + 1이 불편하시다면, 파이썬 math.isqrt 함수 를 통해 math.isqrt(N) + 1로 하시면 됩니다. 물론 그런 오차가 날 정도로 큰 N에 대해 소수판별을 하고 싶다면 그냥 밀러 라빈 소수판별법 쓰시는게 훨씬 낫습니다.
확률적으로 하고 싶으시다면 뤼카 수열 소수판별법 같은 방법도 가능한데, 이 방법도 평범하게 나눠보는 것 보다는 훨씬 복잡합니다.