Visual C++ 2010 으로 컴파일할 경우, 헤더파일 inttypes.h 가 Visual C++ 2010 에는 빠져 있으므로 http://msinttypes.googlecode.com/svn/trunk/inttypes.h 를 가져와서 아래의 소스와 동일한 디렉토리에 두고 컴파일한다.

char * 타입의 C 스트링으로 부터 long long 타입의 정수로 파싱하려면 C99 에서 정한 함수 strtoll 함수를 쓰면 되는데 이 함수 역시 Visual C++ 2010 에는 빠져 있으므로, _strtoi64 함수로 대체하기 위해 소스의 앞 부분에 매크로 정의 #define strtoll _strtoi64 를 추가하였다.

또 main 함수 안에서 사용된 llabs 함수는 long long 타입의 정수의 절댓값을 구하는 함수이다. abs 함수를 쓰면 절댓값이 int 타입의 값으로 나오므로 long long 타입에 대하여는 잘못된 절댓값을 가져올 수 있다.

 

* gcc 4.6.* 또는 Visual Studio 2010 의 cl 로 컴파일되는 C 소스

/*
 * Filename: eulerPhiGoodC_01.c
 *
 *  Purpose:
 *          Calculate the Euler phi function of a given nonzero integer
 *          with using its muliplicative property.
 *
 *          The Euler phi function of a given positive integer n is defined as.
 *          the number of positive integers which are relative prime to n
 *          from 1 to n.
 *
 * Compile: gcc -o eulerPhiGoodC_01 eulerPhiGoodC_01.c
 *    Or
 * Compile: cl /DVC2010 eulerPhiGoodC_01.c
 *
 * Execute: ./eulerPhiGoodC_01 [nnn]
 *    Or
 * Execute: eulerPhiGoodC_01 [nnn]
 *
 *  Date: 2011. 11.  7 (Mon)    eulerPhiGoodPython_01.py
 *  Date: 2013. 12. 13 (Fri)    eulerPhiGoodC_01.c
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>
#ifdef VC2010
  #include "inttypes.h"
  #define strtoll _strtoi64
#else
  #include <inttypes.h>
#endif
 
void printUsage()
{
    printf("Usage: eulerPhiGoodC_01 [nnnnnn]\n");
    printf("nnnnnn should be an integer.\n");
}

long long gcd(long long a, long long b)
{
    long long a1 = abs(a);
    long long b1 = abs(b);
    long long q = a1;
    long long r = b1;
    long long t;
    while (r != 0)
    {
        t = r;
        r = q % r;
        q = t;
    }
    return q;
}

int divide_each(long long n)
{
    long long a = 3;

    if ((n & 0x1) == 0 || n <= 1)
        return 0;
    else if (n == 2)
        return 1;

    while (a*a <= n)
    {
        if ((n % a) == 0)
            return 0;
        a += 2;
    }
    
    return 1;
}

int is_prime(long long n)
{
    return divide_each(n);
}

long long next_prime(long long n)
{
    long long k = llabs(n);
   
    k = k + 1;
    if (k <= 2)
    {
        return 2LL;
    }

    if ((k % 2) == 0 && k > 2)
        k += 1;
    while (!is_prime(k))
        k += 2;

    return k;
}


 

int main(int argc, const char *argv[])
{
    long long n = 0;
    long long cnt = 0;
    long long nphi = 0;
    long long sum = 0;
    long long t = 0;
    long long g = 1;
    long long m = 0;
    long long p = 1;
    long long *factors = (long long *)malloc(sizeof(long long)*200);
    long long nfactor = 0;
    long long ndivisor = 1;   // the number of positive divisors of the input integer
    long long nsum = 1;       // the sum of all positive divisors of the input integer
    int ndx = 0;        // index of storing position factor in factors
    long long *divisors = NULL;
    long long last_prime;
    int i, j, k;

    if (argc != 2)
    {
        printUsage();
        exit(1);
    }
    else
    {
        n = strtoll(argv[1], NULL, 10);
        n = llabs(n);
        if (n != 0)
        {
            t = n;
            k = 0;
            m = 0;  // multiplicity of prime factor
            ndivisor = 1;   // the number of positive divisors of the input integer
            nsum = 1;       // the sum of all positive divisors of the input integer
            nphi = 1;       // the numner of positive integers relative prime to the input integer
    
            p = 1;
            while (t > 1 && p*p <= n)
            {
                p = next_prime(p);
                m = 0;
                while (t % p == 0)
                {
                    t = (long long)(t / p);
                    m = m + 1;
                }

                if (m > 0)
                {
                    factors[ndx] = p;
                    ndx += 1;
                    factors[ndx] = m;
                    ndx += 1;
                    nfactor += 1;
                    ndivisor *= (m + 1);
                    nsum *= (long long)((pow(p, m+1) - 1)/(p - 1));
                    nphi *= (long long)(pow(p, m - 1)*(p - 1));
                }
            }
    

            if (is_prime(t))
            {
                m = 1;
                factors[ndx] = t;
                ndx += 1;
                factors[ndx] = m;
                ndx += 1;
                nfactor += 1;
                ndivisor *= (m + 1);
                nsum *= (long long)((pow(t, m+1) - 1)/(t - 1));
                nphi *= (long long)pow(t, m - 1)*(t - 1);
                m = 0;
            }
                
            printf("Prime factorization: %"PRId64" = ", n);
            for (i = 0 ; i < 2*nfactor; i += 2)
            {
                printf("%"PRId64"^{%"PRId64"} ", factors[i], factors[i + 1]);
            }
            printf("\n");
            printf("The number of positive divisors:  tau(%"PRId64") =  %"PRId64".\n", n, ndivisor);
            printf("The sum of all positive divisors:  sigma(%"PRId64") = %"PRId64".\n", n, nsum);
            printf("The number of positive integers relatively prime:  phi(%"PRId64") = %"PRId64"\n", n, nphi);
            if (nsum == n + 1)
                printf("The integer %"PRId64" is a prime number.\n", n);
            else
                printf("The integer %"PRId64" is not a prime number.\n", n);

            divisors = (long long *)malloc(sizeof(long long)*ndivisor);

            cnt = 0;
            ndx = 0;
            divisors[ndx] = 1;
            ndx += 1;
            cnt = 1;
            for (i = 0; i < 2*nfactor; i += 2)
            {
                p = factors[i];
                m = factors[i + 1];
                for (k = 1; k <= m; k++)
                {
                    for (j = 0; j < cnt; j++)
                    {
                        divisors[ndx] = divisors[j]*pow(p, k);
                        ndx += 1;
                    }
                }
                cnt = ndx;
            }
            printf("The positive divisors of %"PRId64" are\n", n);
            for (i = 0; i < ndivisor - 1; i++)
            {
                printf("%"PRId64", ", divisors[i]);
            }
            printf("%"PRId64".\n", divisors[ndivisor - 1]);
        }
    }
 
    free(factors);
    free(divisors);
 
    return 0;
}

 

 

실행> eulerPhiGoodC_01 240
Prime factorization: 240 = 2^{4} 3^{1} 5^{1}
The number of positive divisors:  tau(240) =  20.
The sum of all positive divisors:  sigma(240) = 744.
The number of positive integers relatively prime:  phi(240) = 64
The integer 240 is not a prime number.
The positive divisors of 240 are
1, 2, 4, 8, 16, 3, 6, 12, 24, 48, 5, 10, 20, 40, 80, 15, 30, 60, 120, 240.

실행> eulerPhiGoodC_01 24345
Prime factorization: 24345 = 3^{2} 5^{1} 541^{1}
Prime factorization: 24345 = 3^{2} 5^{1} 541^{1}
The number of positive divisors:  tau(24345) =  12.
The sum of all positive divisors:  sigma(24345) = 42276.
The number of positive integers relatively prime:  phi(24345) = 12960
The integer 24345 is not a prime number.
The positive divisors of 24345 are
1, 3, 9, 5, 15, 45, 541, 1623, 4869, 2705, 8115, 24345.

실행> eulerPhiGoodC_01 2434500
Prime factorization: 2434500 = 2^{2} 3^{2} 5^{3} 541^{1}
The number of positive divisors:  tau(2434500) =  72.
The sum of all positive divisors:  sigma(2434500) = 7694232.
The number of positive integers relatively prime:  phi(2434500) = 648000
The integer 2434500 is not a prime number.
The positive divisors of 2434500 are
1, 2, 4, 3, 6, 12, 9, 18, 36, 5, 10, 20, 15, 30, 60, 45, 90, 180, 25, 50, 100, 7
5, 150, 300, 225, 450, 900, 125, 250, 500, 375, 750, 1500, 1125, 2250, 4500, 541
, 1082, 2164, 1623, 3246, 6492, 4869, 9738, 19476, 2705, 5410, 10820, 8115, 1623
0, 32460, 24345, 48690, 97380, 13525, 27050, 54100, 40575, 81150, 162300, 121725
, 243450, 486900, 67625, 135250, 270500, 202875, 405750, 811500, 608625, 1217250
, 2434500.

실행> eulerPhiGoodC_01 481000000008
Prime factorization: 481000000008 = 2^{3} 3^{1} 11^{1} 73^{1} 24958489^{1}
The number of positive divisors:  tau(481000000008) =  64.
The sum of all positive divisors:  sigma(481000000008) = 1329788347200.
The number of positive integers relatively prime:  phi(481000000008) = 143760890
880
The integer 481000000008 is not a prime number.
The positive divisors of 481000000008 are
1, 2, 4, 8, 3, 6, 12, 24, 11, 22, 44, 88, 33, 66, 132, 264, 73, 146, 292, 584, 2
19, 438, 876, 1752, 803, 1606, 3212, 6424, 2409, 4818, 9636, 19272, 24958489, 49
916978, 99833956, 199667912, 74875467, 149750934, 299501868, 599003736, 27454337
9, 549086758, 1098173516, 2196347032, 823630137, 1647260274, 3294520548, 6589041
096, 1821969697, 3643939394, 7287878788, 14575757576, 5465909091, 10931818182, 2
1863636364, 43727272728, 20041666667, 40083333334, 80166666668, 160333333336, 60
125000001, 120250000002, 240500000004, 481000000008.

실행> eulerPhiGoodC_01 481000000009
Prime factorization: 481000000009 = 83^{1} 347^{1} 3361^{1} 4969^{1}
The number of positive divisors:  tau(481000000009) =  16.
The sum of all positive divisors:  sigma(481000000009) = 488441580480.
The number of positive integers relatively prime:  phi(481000000009) = 473599042
560
The integer 481000000009 is not a prime number.
The positive divisors of 481000000009 are
1, 83, 347, 28801, 3361, 278963, 1166267, 96800161, 4969, 412427, 1724243, 14311
2169, 16700809, 1386167147, 5795180723, 481000000009.

실행> eulerPhiGoodC_01 481000000001
Prime factorization: 481000000001 = 367^{1} 1310626703^{1}
The number of positive divisors:  tau(481000000001) =  4.
The sum of all positive divisors:  sigma(481000000001) = 482310627072.
The number of positive integers relatively prime:  phi(481000000001) = 479689372
932
The integer 481000000001 is not a prime number.
The positive divisors of 481000000001 are
1, 367, 1310626703, 481000000001.

 

 

 

Posted by Scripter

댓글을 달아 주세요