c语言 合数分解

合数分解

【问题描述】

由数学基本定理可知：任何一个大于1的非素数整数（即合数）都可以唯一分解成若干个素数的乘积。编写程序，从控制台读入一个合数（合数的大小不会超过int数据类型表示的范围），求这个合数可以分解成的只出现一次的素数。例如合数1260分解成素数乘积为：22335*7,2和3出现两次，5和7出现一次，所以求得的结果为5和7。

【输入形式】

从控制台输入一个合数。

【输出形式】

在标准输出上按照由小到大的顺序输出分解后的只出现一次的素数，各素数之间以一个空格分隔，最后一个素数后也可以有一个空格。若没有只出现一次的素数，则什么都不输出。

【输入样例】

6154380

【输出样例】

5 29 131

【样例说明】

输入的合数为6154380，其分解成的素数乘积为：2 *2 *3 *3 *3 *3 *5 *29 *131，其中2出现两次，3出现4次，5、29和131只出现一次，所以只输出5、29、131。

偶然间想起来这个题目，如果我们没有去分析合数的性质直接去做的话，就会很麻烦。
如果没有分析合数，我们得先构造一个素数的数列，然后再循环找出能整除的素数，再去掉这个商和的重复数，再输出。
这时分析一下这个合数，题目中很明确的告诉我们这个是被唯一整除的，
然后所有的整数都可以用素数的乘积的形式表示，也就是说我们这时候没有必要去构造一个素数的数组，只要我们从2开始往返循环就可以完成素数的构造。这时这个题目的输出输入我们也要观察一下，很明显这个输出
22333*……从小到大排列，也就是说如果存在重复素数，那么必定相邻。然后在偶然启发下代码`

#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    int i=2,flag=0;//用来标记相邻的数重复个数
    for(;i<=n;)
    {
        if(n%i==0)
        {
           n/=i;
           flag++;
        }
        else
        {
           if(flag==1)printf("%d ",i);//若只有一个就符合题意输入
           i++;//若无法整除就需要往后加
           flag=0;//标记清空
        }
   }
   if(flag==1)printf("%d ",i);//如果最后一个数就重复一次就输出
   return 0;
   }