1059 Prime Factors (25分)

1. 题目

2. 思路

先求解出int范围内的所有素数，把输入x分别对素数表中素数取余，判断是否为0，如果为0继续除该素数知道余数不是0，遍历到sqrt(x)就够了

3. 注意点

输入数为1的情况，输出1=1

4. 代码

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

#define MAXN 100000

// 长度10够用的，前10个素数的乘积已经超过int了

struct fra{

	int x;

	int n;

}f[10]; 

void show(fra a[], int size, int x){

	printf("%d=", x);

	int i = 0;

	for(i=0;i<size-1;i++){

		if(a[i].n == 1){

			printf("%d*", a[i].x);

		}else{

			printf("%d^%d*", a[i].x, a[i].n);

		}

	}

	if(a[i].n == 1){

		printf("%d", a[i].x);

	}else{

		printf("%d^%d", a[i].x, a[i].n);

	}

}

bool isPrime[MAXN];

int prime[MAXN];

void init(){

	int count = 0;

	for(int i=2;i<=MAXN;i++){

		if(isPrime[i] == false){

			prime[count++] = i;

			for(int j=i+i;j<MAXN;j+=i){

				isPrime[j] = true;

			}

		}

	}

}

int main(){

	int x;

	init();

	scanf("%d", &x);

	int x_copy = x;

	if(x == 1){

		printf("1=1");

		return 0;

	}

	int count = 0;

	int sqr = sqrt(x);

	for(int i=0;i<sqr;i++){

		if(x % prime[i] == 0){

			f[count].x = prime[i];

			f[count].n = 1;

			x/=prime[i];

			while(x % prime[i] == 0){

				f[count].n++;

				x/=prime[i];

			}

			count++;

		}

		if(x == 1){

			break;

		}

	}

	if(x != 1){

		f[count].x = x;

		f[count].n = 1;

		count++;

	}

	show(f, count, x_copy);

	return 0;

}

巴特西

1059 Prime Factors (25分)

1059 Prime Factors (25分)

1. 题目

2. 思路

3. 注意点

4. 代码

最新文章

热门文章