基础练习——分解质因数

题目描述

求出区间[a,b]中所有整数的质因数分解。

输入

输入两个整数a，b。

输出

每行输出一个数的分解，形如k=a1*a2*a3...(a1<=a2<=a3...，k也是从小到大的)(具体可看样例)

样例输入

3 10

样例输出

3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5

提示
先筛出所有素数，然后再分解。

本题开始是从因数方面入手的，迟迟找不到解决口，之后突然间意识到，求的是某个数的质因数之积，果断从结果入手。

开始还糊涂地eratosthenes筛了，忘了只能作为判断条件。。

不过改过之后还是把数组元素值作为判断条件，用下标输出，完美。

 

不过之前因为这个原因搜了下博客，发现了和eratosthenes筛一个原理的免写了个函数的做法:

直接从2开始判断，能整除就输出，不能就＋1， 当时还在疑惑这会不会把某些合数误放进去。

现在明白了，这不是和eratosthenes筛一个原理吗，只不过筛的时候是直观的一个个判断，而这里是一个整除解决所有的可能问题。

eg:

8 = 2*2*2，根本没机会见到4.

10 = 2*5

12 = 2 * 2 * 3

14 = 2 * 7

39 = 3 * 13

☆121 = 11 * 11

等一系列情况，你根本没法见到合数，或者是合数根本不是他们的因数。

所以就OK啦

贴个代码

#include<stdio.h>
#include<math.h>
void pri(int n){
	int len = sqrt(n+0.5), k = 2, x = n;
	printf("%d=", x);
	while(k <= len){
		if(x%k == 0){
			x = x / k;
			if(x > 1){ 
				printf("%d*", k);
				continue;
			}
			if(x == 1)
				printf("%d\n", k);
		}
		k++;
	}
	if(x > 1 && x <= n)
		printf("%d\n", x);
}
int main()
{
	int n, c, d;
	scanf("%d %d", &c, &d);
	for(n = c; n <= d; n++){
		pri(n);
	}
	return 0;
}