소수의 판별

 

소수(Prime Number)

소수란 1보다 크면서 1과 자기 자신만을 약수로 갖는 자연수이다.

1은 소수가 아니다는 점에 주의할 것.

 

기본 방법

2부터 n - 1까지 순회하면서 나누어 떨어지는 수가 있는경우 false를 리턴한다.

시간 복잡도는 O(N) 이다.

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

 

N의 약수는 무조건 sqrt(N)의 범위에 존재한다.

곱셉을 할때는 두 수가 같을때 가장 큰 수가 나온다.

-> 결과값이 같다면 곱하는 두 수가 같은 경우가 제일 크다.   

 

는 성질을 이용해 sqrt(N) 까지만 순회한다.

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

 

 

소인수 분해

2부터 순회하면서 약수를 찾을때마다 리스트에 더하면 된다.

List<int> list = new List<int>(); 
for (int i = 2; i * i <= n; i++) 
{
    while(n % i == 0)
    {
        list.Add(i);
        n /= i;
    }
}

if(n > 1)
	list.Add(n);

 

 

 

에라토스테네스의 체도 별도로 정리필요.