소수란?
자기자신과 1 이외에는 어떠한 정수라도 나뉘어 떨어지지 않는 수를 소수라 한다.
즉 약수가 1과 자기자신, 2개뿐이다.
❗️첫 번째 방법
가장 단순하게, 2부터 n까지 모든 정수로 나누어보는 방법이다.
판별하고자 하는 수까지 모두 확인해야하므로 O(n)의 시간복잡도를 가진다.
❗️두 번째 방법
2부터 n/2까지 모든 정수로 나누어보는 방법이다.
조금만 생각을 해보면, 절반을 초과하는 수는 확인이 필요 없기 때문이다.
자기자신을 제외하고 절반을 초과하는 숫자에서 나눴을때 나머지가 0이되는 숫자는 나올수가 없다.
왜냐하면 절반을 초과하면 나눴을 때1.xxx가 나올 것인데,
몫이 1이고 나머지가 0인 것은 자기자신이기 때문이다.두 번째 방법의 시간복잡도 또한 O(n)이 된다.
❗️세 번째 방법
2부터 √n 까지 모든 정수로 나누어보는 방법이다.
두 번째 방법과 비슷한 원리인데, 약수들의 중간값을 이용하는 것이다.
예를 들어, 40의 약수를 살펴보면 다음과 같은데
1, 2, 4, 5, 8, 10, 20 ,40
(1,40) (2,20) (4,10) (5,8)의 쌍으로 이루어져 있다.
√40은 6.xxx이고 40의 약수들의 중간에 있다.그러므로 이후의 값들은 확인할 필요가 없다는 것이다. 어차피 약수 쌍의 나머지 한 값이기 때문이다.
❗️네 번째 방법
에라토스테네스의 체
고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법. 이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다.
위와 같이 특정 수의 배수는 소수가 될 수 없다는 것에 착안하여 2부터 N까지의 수에서 배수를 모두 제거한 뒤 나믄 수를 소수로 판별하는 방식이다.
