分解质因数

电玩女神 2022-06-01 13:52 272阅读 0赞

问题描述

求出区间\[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

提示

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

数据规模和约定

2<=a<=b<=10000

思路：先用函数求出10000以内的质数，存到数组里。然后用双层循环，外层控制\[a,b\]范围，内层有三个，第一个循环作用是直接输出\[a,b\]范围内的质数，第二个循环的作用是对非质数的数进行一个判断处理，判断思路：对要分解的数进行除法操作，然后在用if语句判断是否可以整除，如果可以整除，我们将存到数组里（输出格式需要，我也不知道怎么处理这种输出格式，只能用这种笨方法）。假设这个数字第一次可以被（为了方便理解，我用2代替一下）2整除，那么第二次它也同样可能2整除，所以我们要将第二个循环从新由2的下标开始循环。这里我是用if加上0和1的方式判断条件，当然整篇代码都用了不少这样的例子。第三个循环是对第二个循环求出的值按照题目给出的标准的输出格式输出。（小白还请多多关照）

#include <stdio.h>
    #include <windows.h>
    
    int fun22(int * a)
    {
    	int i, j, m = 0, true_ = 0;
    	
    	for(i = 2; i < 10000; i++)
    	{
    		true_ = 0;
    		for(j = 2; j < i / 2 + 1; j++)
    		{
    			if(i % j == 0)
    				true_ = 1;	
    		}
    		if(!true_)
    			a[m++] = i;	
    	}
    	return m;
    }
    
    void fun21(void)
    {
    	int n, m, x, y;
    	int i, j, true_;
    	int a[5000], k, b[10000], kk = 0;
    	
    	scanf("%d%d", &n, &m);
    	k = fun22(a);
    	for(n ; n <= m; n++)
    	{
    		j = n;	true_ = 0;
    		for(i = 0; i < k; i++)
    		{
    			if(n == a[i])
    			{
    				printf("%d=%d\n", n, n);
    				true_ = 1;
    				break;
    			}		
    		}
    		if(true_)
    			continue;
    		memset(b, 0, sizeof(b));
    		kk = 0; i = 0;
    		while (i < k)
    		{
    			x = j / a[i];
    			true_ = 0;
    			if(j == a[i] * x)
    			{
    				j = x;
    				
    				b[kk++] = a[i];
    				y = j / a[i]; 	
    				if(j != 0 && j == y * a[i])
    					true_ = 1;			
    			}
    			if(j == 0 || a[i] > n)
    				break; 
    			if(true_)
    				i = 0;
    			else
    				i++; 
    		}
    		printf("%d=", n);
    		for(i = 0; i < kk; i++)
    		{
    			if(i == kk - 1)
    				printf("%d", b[i]);
    			else 
    				printf("%d*", b[i]);

//printf("%d%c", b[i], n == kk - 1 ? '*': '');
    		}
    		if(n < m)
    			printf("\n");
    	}
    }
    
    int main()
    {	
    	system("color 0a");	
    	fun21();
    	return 0;
    }