U E D R , A S I H C RSS

Factorial Factors/문보창

소감

2006-01-19 Accepted 1.434 4344
현태한테 설명 듣고 완성.

코드

~cpp 
// 884 - Factorial Factors
#include <iostream>
using namespace std;

#define MAXN 1000000

static int fact[MAXN+1];

void findFact()
{
	int i, j;
	for (i = 2; i <= MAXN; i++)
	{
		if (fact[i] == 0)	// 소수
		{
			fact[i] = 1;
			for (j = i + i; j <= MAXN; j+=i)
				fact[j] = i;
		}
		else				// 합성수
			fact[i] = fact[i/fact[i]] + fact[fact[i]];
	}
	for (i = 2; i < MAXN; i++)
		fact[i+1] += fact[i];
}

int main()
{
	int n;
	findFact();
	while (cin >> n)
		cout << fact[n] << endl;
	return 0;
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:15
Processing time 0.0098 sec