A1059 Prime Factors (25 point(s))

素数因子计算

1. 原文

原题

Given any positive integer N, you are supposed to find all of its prime factors, and write them in the format N = $p_1^{k1}$×$p_2^{k2}$⋯×$p_m^{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

2. 解析

特殊判断：n==0 0=0 n==1 1=1

预存$10^5$内的素数结果，当n%prime[i]==0时，说明该素数可用，统计个数cnt++

3. AC代码

#include<cstdio>
const int maxn=100010;
int prime[maxn]={};
bool visit[maxn]={false};
int idx=0;
void init()
{
	for (int i = 2; i < maxn; ++i)
	{
		if (visit[i]==false)
		{
			prime[idx++]=i;
			//printf("%d\n", i);
			for (int j = i+i; j < maxn; j+=i)
			{
				visit[j]=true;
			}
		}
	}
}
int main()
{
	init();
	long long n;
	scanf("%lld",&n);
	if (n==0)
	{
		printf("0=0\n");
		return 0;
	}
	if (n==1)
	{
		printf("1=1\n");
		return 0;
	}
	printf("%lld=",n);
	int key=0;
	for (int i = 0; i < idx; ++i)
	{
		int flag=0; int cnt=0;
		while(n%prime[i]==0){
			flag=1;
			cnt++;
			n/=prime[i];
		}
		if (flag==1)
		{
			if (key>0)
			{
				printf("*");
			}else{
				key++;
			}
			printf("%d",prime[i]);
			if (cnt>1)
			{
				printf("^%d",cnt);
			}
		}
		if (n==0)
		{
			break;
		}
	}
	printf("\n");
	return 0;
}