1.약수 구하기

n 의 약수를 구하여 보자.

방법 1. 무작정 하기

n 을 1 부터 n 까지 나누어가면서 나누어지면 약수 .

   cnt  = 0;
   for( i = 1 ; i <= n ;i++){
     if ( n % i == 0 ) printf("%d ",i);
   }
   

방법 2. 중복 피하기

n 이 20 인 경우인 경우 약수

      1  20
      2  10
      4   5
      5   4 --- 이 부분부터 중복 
      10 2
      20 1
      

중복을 피할 수 있는 경계선이 √n 이다.

      for( i = 1 ; i*i < n ; i++){
         if ( n % i == 0 ) printf("%d %d",i,n/i); //약수는 쌍으로 존재
      }

      if ( i*i == n ) printf(" %d",i); //n 이 제곱수인 경우
      

* 약수의 개수를 구하는 경우에도 이를 이용하면 빠르게 구할 수 있다.

위 소스에서 한 번쯤 생각하고 넘어가야 할 것은

• 제곱수를 제외하고는 약수는 쌍으로 존재하고
• 즉 제곱수를 제외한 모든 수의 약수의 개수는 짝수개

2.소인수 구하기

1. n 이 소수인지 는 2 .. √n 까지 나누어 보고 나누어 지지 않으면 소수 입니다.

   예를 들어 설명 하겠습니다. n 이 616 이라면 소인수는 아래와 같습니다.

   2 2 2 7 11

   √616 = 24.8xxx 이니 2 부터 24 까지 나누어 봅니다. 만약 나누어지지 않으면 소수 인데 이 경우 2 로 나누어 집니다.

   그러면 소인수 2 로 나눌수 있을때 까지 나눕니다.

2. 그러면 남는 수는 77 입니다. 이 수에는 소인수 2 는 없습니다.

   그러면 3 .. √77 = 7.xx 이니 3 에서 7 까지 나누어 봅니다. 이 는 1 번의 반복 입니다. 차례대로 나누어 가니 나누어지는 수 중에 소수가 아닌 수는 없습니다.

   int n;

   scanf("%d",&n);

   for( int i = 2 ; i*i <= n ; i++){
      while ( n % i == 0 ) {
         printf("%d ",i);
         n /= i;
      }
   }
   if( n != 1 ) printf("%d",n);

3.약수의 개수 구하기(소인수 분해 이용)

4.약수의 합 구하기(소인수 분해 이용)

출처:dovelet