U E D R , A S I H C RSS

Smith Numbers/신재동

SmithNumbers/신재동

~cpp 
#include <iostream>
#include <vector>
using namespace std;

const int MAX_TEST = 100;

const int MAX_PRIME_NUMBER = 100000;
int MAIN_PRIME_NUMBER[MAX_PRIME_NUMBER] = {0,};

int testCase;

int number;
int smithNumbers[MAX_TEST] = {0,};

void input();
void process(int i);
void output();
int sumPositionOfNumber(int testNumber);
int sumFactorizationOfNumber(int testNumber);
bool isSmithNumber(int n);
int factorization(int testNumber);
void makePrimeNumbers();

void makePrimeNumbers()
{ 
	int primeCount = 0;
    MAIN_PRIME_NUMBER[primeCount++] = 2;

    for (int i = 3; primeCount < MAX_PRIME_NUMBER; i += 2)
    {
		for (int j = 0; j < primeCount; j++)
		{
			if (i % MAIN_PRIME_NUMBER[j] == 0)
				break;
			else if (i / MAIN_PRIME_NUMBER[j] <= MAIN_PRIME_NUMBER[j])
			{
				MAIN_PRIME_NUMBER[primeCount++] = i;
				break;
			} 
		} 
    } 
}

void input()
{
	//number = 4937774;
	cin >> number;
}

int sumPositionOfNumber(int testNumber)
{
	int sum = 0;

	for(int i = 9; i >= 0; i--)
	{
		int devideNum = 1;
		for(int j = 0; j < i; j++)
			devideNum *= 10;

		sum += testNumber / devideNum;
		testNumber %= devideNum;
	}
	return sum;
}

int factorization(int testNumber)
{
	int prime = 1;
	for(int i = 0; i < MAX_PRIME_NUMBER; i++)
	{
		if(testNumber % MAIN_PRIME_NUMBER[i] == 0)
		{
			prime = MAIN_PRIME_NUMBER[i];
			break;
		}
	}
	return prime;
}

int sumFactorizationOfNumber(int testNumber)
{
	int sum = 0;
	int prime;

	while(true)
	{
		prime = factorization(testNumber);
		if(prime == 1)
			break;
		testNumber /= prime;
		sum += sumPositionOfNumber(prime);
	}
	return sum;
}

bool isSmithNumber(int testNumber)
{
	return sumPositionOfNumber(testNumber) == sumFactorizationOfNumber(testNumber);
}

void process(int i)
{
	int testNumber = number;
	while(true)
	{
		if(isSmithNumber(testNumber))
			break;
		testNumber++;
	}
	smithNumbers[i] = testNumber;
}

void output()
{
	for(int i = 0; i < testCase; i++)
	{
		cout << smithNumbers[i] << endl;
	}
}

int main()
{
	makePrimeNumbers();

	cin >> testCase;

	for(int i = 0; i < testCase; i++)
	{
		input();
		process(i);
	}
	output();

	return 0;
}

문제 설명에 나온대로 그냥 무식하게 만듬. --재동

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:03
Processing time 0.0122 sec