소수 판별 알고리즘

소수 판별 알고리즘 O(N)n까지 확인하는 방법이다.소수 판별 알고리즘 O(sqrt(N))이는 아래 과정에 의해 시작된다.A를 합성수 MxN이라고 가정하자.이때 M>=N이라고 하자.M^2>=MxN이고,M>=sqrt(A)이다.따라서 sqrt(A)까지 확인하면 소수인지 합

보통 에라토스테네스의 체를 구현할 때면$i$ 루프( 소수 확인 루프 )를 최대 $N$ 까지 돈다.$j$ 루프( $i$ 배수 루프 )를 $2\\cdot i$ 부터 시작한다.위와 같이 구현하는데최적화 시$i$ 루프를 $\\sqrt N$ 까지 돈다.$j$ 루프를 $i^2$