😆소수 루트n의 시간 복잡도

그냥 외우는 게 아님. : 최근 추가 240210

• 시간 복잡도 logN

  루트 n보다 작거나 같은 수로 나누어 떨어지면 소수가 아님!

bool prime(int n)
{
	if (n < 2)
		return false;


	// i <= 루트 n은 못하므로.
	// i * i < n
	for (int i = 2; i * i <= n; ++i)
	{
		if (n % i == 0)
			return false;
	}

	return true;
}

---

개념

: 약수가 1과 자기자신 밖에 없는 수 , (1을 제외하고)

• 2 , 3 , 5 , 7 , 11 ,,,

• 4 , 6 , 8 , 9 는 약수가 자기 자신말고도 많음.

코드로 구현

1. 간단히 생각할 수 있는 구현

for(int i = 2; i < n; ++i)
{
if(n % i == 0)
{
//소수 아님.
}
}
-> 시간 복잡도 : o(n)

2. n / 2 까지만 진행하면 되지 않을까???

: 왜 이러한 생각을 했따면, 숫자를 반절로 나누었을 때 그 값까지만 진행하면
짝꿍의 값이 나오기 때문.
반절이상이 값으로 나누면 이전에 진행한 넘버는 반드시 나옴.

• n이 27이라고 할 때
  27이 소수인지 아닌지를 확인할 때(일단 소인수는 1 3 9 27 ) 이고
  1 이랑 3까지만 진행하면 짝 꿍인 9와 27에 관해서 소인수인지를 전혀 진행할 필요가 없음.

• n이 23이라고 하면 (일단 소인수는 1 23이다. -> 따라서 소수임.)
  : 위에서 내가 생각한대로 진행하면 11까지만 진행하면 알 수 있음.

• n 이 14라고 하면 (일단 소수 아님.)
  7까지만 진행하더라도 나누어지니까 소수가 아님.

• 코드

for(int i = 2; i * 2 <= n; ++i)
{
	if(n % i == 0) 
    -> 소수
    
}

• 시간 복잡도 : o(n /2 )

3. 루트 n을 생각하자.

왜 이런생각을 했냐면, 어떠한 수에 관해서 제곱근이란
제곱근끼리 곱했을 때 원래 수를 구할 수 있다는 것임.
-> 제곱근 보다 큰값은 반드시 제곱근보다 작은 값과 곱해야만
원래 수를 만들수 있음. 아니면 만들지도 못함.
즉, 제곱근을 기준으로 해서 대칭을 이루고 있음을 숙지해야 함.

• 16을 가지고 생각해보면,
  1 2 4 8 16 이고 여기서의 제곱근인 4까지만 처리하면 된다는 것임.
  그럼 8은 이미 2에서 계산을 했기 때문에 소수유무 진행할 필요가 없음.

• -> 위의 예를 통해 대칭을 만드는 제곱근을 통해 소수 유무 판별이 가능함.

if(n < 2) false;
for(int i = 2; i * i <= n; ++i)
{
	if( n % i == 2) 
    {
    //소수 아님.
    }
    
}

• 시간 복잡도 O(longN)

3. 에라토스테네스의 채 사용하기