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.
