蓝桥杯某C语言算法题解决方案（质因数分解）

蓝桥杯原题：将一个正整数分解质因数例如：输入90，打印出90 = 2 * 3 * 3 * 5。

声明：该题目是否为蓝桥杯原题未知，我是从CSDN上面查到的，仅对该题目进行解决。

这个题与我之前发表过的一些关于检验一个数字是否为素数（质数）的项目相关性极大，如果我们要对一个数字进行质因数分解，首先我们要直到它可能会有哪些质因数。我们必须意识到，如果一个数字是它的因数，那么这个数字一定小于它。因此，它的质因数也一定会小于它。

这就给了我们突破口，首先我们要找到一些“候选素数（Candidates）”，也就是只要这些数字是素数，并且比我们需要检验的数字小，那么它们就有可能是它的质因数，也就是我们所属的候选素数。

单单找到这些素数还不行，我们还需要把他们存储起来以备后面检验它们是否是“真质因数（True prime factors）”。

我必须提示大家，我这次写的项目并非最简单的方法，事实上，我们可以不用数组保存这些候选素数，而是直接在每个素数被找到之后立刻进行判断并且输出，这样会更简单一些。但是我这次不会给你展示这种方法，我展示的是使用了数组的方法，之后我会给出我提到的这个更好的方案，然而这次，我们要解释这个比较容易理解的方案。

下面我们展示完整的代码：

//从2开始第500个素数是3571，因此本程序的arr_store最大储存3571，因此是有数据限制的。
// 基于以上原因，请不要尝试过大的数字。
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void judPrime(int put,int arr[],int* y) {
	int a = put - 1; int trial = 0;
	for (a = put - 1; a > 0; a--) {
		if ((put % a == 0)&&(a!=1)) {
			trial++;
		}
		else if (a == 1) {

		}
	}
	if (trial == 0) {
		arr[*y] = put;
		*y=*y+1;
	}
}
int main()
{
	int input = 0; int judge = 0;
	int x = 2; int arr_store[500] = { 0 };
	int y = 0; int* py = &y;
	printf("请输入你要质数分解的数字：");
	scanf("%d", &input);
	for (x = 2; x < input; x++) {
		if (input % x == 0) {
			judge++;
		}
	}
	x = 2;
	if (judge == 0) {
		printf("输入的数字是素数，其质因数分解结果为：%d*1", input);
	}
	else {
		for (x = 2; x < input; x++) {
			judPrime(x, arr_store,py);
		}
		x = 0;
		while (arr_store[x] != 0) {
			if (input % arr_store[x] == 0) {
				printf("%d*", arr_store[x]);
				input /= arr_store[x];
				x++;
			}
			else {
				x++;
			}
		}
			printf("%d", input);
	}
	return 0;
}

由于我对数组arr_store的大小规定为500，因此我们最多能存下第500个质数，这就导致我们能判断的数字对象事实上是有限制的，一定会有一个比较大或者特殊的数超出我们能判断的范围，之后我会尝试给出不受这种限制的代码，虽然目前我还没有什么很好的头绪。