2018京東筆記試験——整備

・整除
牛は除去に非常に興味を持っている.牛の先生は彼に1つの問題を配置しました:牛の先生はnを与えて、それから牛は1からnの間(1とnを含む)のすべての整数で除去できる最小の数を答える必要があります.牛が困ったので、プログラミングして彼にこの問題を解決してほしい.
まず,1より大きい整数を複数の素数で乗算して表すことができるという考え方を解く.これは実はよく理解して、数は质数と合数にほかならなくて、质数は1と自分で除くことしかできなくて、合数が除いた后に最后にも质数しか残っていません.したがって逆に,我々が要求するのは最小公倍数に相当し,1~nの各数の最小素数の個数を求め,乗算すれば解決できる.
問題を解くときに配列を用いることができ,配列の下付き文字は1~nに相当し,格納されたintは個数に相当するので,解決がより便利である.
コードは次のとおりです.

#include
#include
using namespace std;

void Put(int n,int arr[20000])
{
	int i;
	int j;
	for (i = 1; i <= n; i++)
	{
		int k = i;
		for (j = 2; j*j <= n; j++)
		{
			int s = 0;
			while (k%j == 0)
			{
				s++;
				k = k / j;
			}
			arr[j] = max(arr[j], s);
		}
		if (k > 1)
		{
			arr[k] = max(arr[k], 1);
		}
	}
}

int main()
{
	int n=0;
	int arr[20000] = {0};
	scanf("%d", &n);
	Put(n, arr);
	long long res = 1;
	for (int j = 1; j <= n; j++)
	{
		if (arr[j] > 0)
		{
			for (int m = 1; m <= arr[j]; m++)
			{
				res = res*j%987654321;
			}
		}
	}
	printf("%lld", res);
	system("pause");
	return 0;
}