分解整数

yxjoey posted @ 2008年5月28日 07:13 in C语言 with tags c 程序 , 2691 阅读

今天在网上闲看，发现最近正在举行2008年百度之星大赛，于是看看了历年试题，挺有意思的
2005年有一道题目是这样的

题目描述：一个正整数有可能可以被表示为 n(n&gt;=2) 个连续正整数之和，如：

15=1+2+3+4+5

15=4+5+6

15=7+8

请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。

输入数据：一个正整数，以命令行参数的形式提供给程序。

最近正好在找实习，肯定会遇到当场写代码的，于是写下这个程序算个练习

#include <stdio.h>
void decomposed_sum(int num);
void decomposed_product(int num);
 
int main(int argc, char *argv[]){
  int num =  atoi(argv[1]);
  printf("========= sum decompsition ========\n");
  decomposed_sum(num);
  printf("========= product decompsition ========\n");
  decomposed_product(num);
}
/* To decompse as sumation is almost the same as to decompse as production
 * Assume the number can be decompsed as n numbers starting from a
 *    num = (2a+n-1)*n/2
 * => 2num = (2a+n-1)*n
 *
 */
void decomposed_sum(int num){
  num = 2*num;
  int n;
  int start;
  int tmp;
  int k;
  for(n=2; n*n < num; n++){
    if(num % n == 0){
      tmp = num/n;
      if(n%2||tmp%2){
        start = (tmp-n+1)/2;
        printf("%d = %d", num/2, start);
        for(k=1; k<n; k++)
          printf("+%d", start+k);
        printf("\n");
      }
    }
  }
}
 
void decomposed_product(int num){
  if(num<2)
    return;
  int k=2;
  printf("%d = ", num);
  while(k*k<=num){
    while(num%k == 0){
      printf("%d  ", k);
      num /= k;
    }
    k++;
  }
  if(num>1)
    printf("%d", num);
  printf("\n");
}
 

原来没写过分解质因数，顺便也写了一边

yxjoey@yxjoey-laptop:~/Sandbox$ ./decompose 300

========= sum decompsition ========

300 = 99+100+101

300 = 58+59+60+61+62

300 = 34+35+36+37+38+39+40+41

300 = 13+14+15+16+17+18+19+20+21+22+23+24+25+26+27

300 = 1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+21+22+23+24

========= product decompsition ========

300 = 2  2  3  5  5