[소수 & 약수] Prime | C++ / Cpp

 

거 참 제목 하나 영어로 썼다고 간지나는 거 보소.

 

 

이전에 에라토스 테네스의 체를 포스팅 한 적이 있다.

https://dusty-wznt.tistory.com/19?category=1061713 

이때는 그냥 코드 구현만 하고 자세한 설명이 없었는데 수업을 듣다가 원리를 깨달아 버렸다.

 

만약 N이 prime이 아니라면

두 positive integer a,b >1에 대하여

n=a*b로 나타낼 수 있다.

이 경우 a or b는 반드시 √n 을 넘지 않는다.

 

bool prime(int n){
	if(n<2) return false;
    for(int x=2,x*x<=n; x++){
    	if(n%x == 0) return false;
    }
    return true;
  }

 

위의 prime 함수는 파라미터로 들어온 정수 n의 값이 소수인지 알아보는 함수로

추가적으로 뇌피셜을 살짝 올리자면

x가 n의 positive integer일 때 x의 최대값은 n=x**2인 경우이다.

때문에 for문에 조건에 x*x <=n을 조건으로 제시하였다.

 

위의 방법을 사용하여 O(√n) 시간에 n을 prime factorization할 수 있다.

 

아래 코드를 보자.

vector<int> factors(int n){
	vector<int> f;
    for (int x=2;x*x<=n;x++){
    	while(n%x==0){
        	f.push_back(x);
            n /= x;
        }
    }
    if(n>1) f.push_back(n);
    return f;
}

위의 코드는 값이 작은 순서대로 n을 prime factorize 한다. 

기본적으로 우리가 할 수 있는 소인수분해 방법을 코드로 구현하였다고 보면 된다.

• x는 벡터 f에 저장하여 prime factorization을 완성한다.
• 만약 for 문이 종료되었음에도 불구하고 n의 값이 1보다 크다면 n은 소수이므로
• f에 n을 push하여 prime factorization을 종료한다.

 

다음 포스팅에 에라토스 테네스의 채를 업데이트하여 더 자세하게 포스팅 해 놓겠다.

 

 

빠샤