230624 Today I Learned

어제 시간관계상 정리를 못한 문제를 오늘 정리해보았다.

소수 판별 방법

1. n보다 작은 자연수로 나눠서 나머지 확인하기

for(int i = 2; i < n; i++){
	if(n % i == 0) return false;
    }
return true;

• 시간복잡도 상으로 O(n)이므로 비효율적이다.

2. for문으로 2~√n까지 나눠서 나머지 확인하기

• 36을 예로 들어보면 36의 약수는 1,2,3,4,6,9,12,18,36이다.
  1x36, 2x18, 3x12, 4x9, 6x6, 9x4, 12x3, 18x2, 36x1 에서 36의 제곱근인 6x6을 기준으로 양쪽이 대칭인 것을 볼 수 있다.
  따라서 소수 판별시 2~√n까지만 나머지를 확인해봐도, √n 다음값부터는 더 확인할 필요가 없다.

//	for (int i = 2; i * i <= n; i++)도 된다.
    for (int i = 2; i<= Math.sqrt(n); i++){
      if (n % i == 0) return false;
    }
    return true;

• 시간복잡도상 O(√n)이다.

3. 그 외에 에라토스테네스의 체라는 방법이 따로 있는데 이 부분은 추후 TIL에 따로 정리를 해보려한다.