(알고리즘) 소수

<첫번째 방법>
소수 N=a*b

제일 작은 소수는 2이므로 b는 최대 N/2이다.

즉 , int i=2 부터 i<=N/2까지 탐색하면 된다.

하지만 시간 복잡도는 여전히 O(n)이다.

<두번째 방법>

소수인 숫자 N= a*b일 때, 두 수중 하나는 a<=루트N 또는 b<=루트 N이다.

만약 두 수 모두 a>루트N and b>루트 N 이면 a*b는 N보다 커진다.

a<=b라고 하면

예를들어, 루트 24=4.xxxxx
그러면 숫자 a는 2, 4, 6, 8, 12라 했을 때, 2,3,4 계산해보면된다.

즉,
  for(int i=2;i*i<=N;i++){
    if(N%i==0)
        return false;
 }
 return true;

결국 시간복잡도는 O(루트N이다)

<에라토스테네스의 체>

N=100인 소수의 갯수를 찾는다 치면
2가 소수이므로 2의배수는 모두 지운다.
3이 소수이므로 3의배수를 지운다
5가 소수이므로 5의 배수를 지운다.
.....
N는 10까지만 시행한다.


*백준-골드바흐의 추측 문제에서
N의 범위가 1백만인데 그 소수를 저장하고 탐색하는 것이  소수를 true,false로 한 것보다 빠르다. 그 이유는 루트N까지가 리스트에 담겨잇으므로.