Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

PAT 1059. Prime Factors

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = p1^k1 * p2^k2 *…*pm^km.

Input Specification

Each input file contains one test case which gives a positive integer N in the range of long int.

Output Specification

Factor N in the format N = p1^k1 * p2^k2 *…*pm^km, where pi’s are prime factors of N in increasing order, and the exponent ki is the number of pi — hence when there is only one pi, ki is 1 and must NOT be printed out.

Sample Input

97532468

Sample Output

97532468=2^2*11*17*101*1291

解答

#include <cstdio>

int main()
{
	long int n, old; scanf("%d", &n); old = n;
	if (n == 1) { printf("1=1\n"); return 0; }

	long int p[1000], exp[1000], id = 0;
	for (long int i = 2; i * i <= n; i++)
		if (n % i == 0)
		{
			p[id] = i, exp[id] = 0;
			while (n % i == 0) n /= i, exp[id]++;
			id++;
		}
	if (n != 1) p[id] = n, exp[id] = 1, id++;

	printf("%d", old);
	for (int i = 0; i < id; i++)
	{
		printf("%s", i==0 ? "=" : "*");
		if (exp[i] == 1) printf("%d", p[i]);
		else printf("%d^%d", p[i], exp[i]);
	}
	printf("\n");
	return 0;
}
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论