华为机试——将一个数分解成两个质数之和
题目描述
* 题目描述:数字分解,将一个数字分解成两个质数相加 * 输入描述:给定数字 * 输出描述:两个质数之和 * 输入示例:10 * 输出示例:10=3+7
代码实现
/************************************************* * 题目描述:数字分解,将一个数字分解成两个质数相加 * 输入描述:给定数字 * 输出描述:两个质数之和 * 输入示例:10 * 输出示例:10=3+7 * 注意事项:Linux下编译时需要连接库,编译参数:-lm *************************************************/ #include <stdio.h> #include <string.h> #include <stdlib.h> #include <unistd.h> #include <math.h> #define NUM_SIZE 100 int g_point = 0; /* 判断一个数是否为质数(素数) */ /* 返回值:0:不是素数 1:是素数 */ int is_prime(int src) { int i; /* 两个较小数另外处理 */ if(src ==2|| src==3 ) return 1 ; /* 不在6的倍数两侧的一定不是质数 */ if(src %6!= 1&&src %6!= 5) return 0 ; int tmp = sqrt( src); /* 在6的倍数两侧的也可能不是质数 */ for(i= 5;i <=tmp; i+=6 ) { if(src %i== 0||src %(i+ 2)==0 ) return 0 ; } /* 排除所有,剩余的是质数 */ return 1 ; } /* 将数字分解成两个质数 */ int div_num(int src,int* des) { int i; for(i=2;i<sqrt(src);i++) { if(is_prime(i) && is_prime(src-i)) { des[g_point] = i; g_point ++; } } return 0; } int main() { int input=0; int* des; int i; #ifdef DEBUG printf("[提示]:输入一个数进行分解:"); #endif scanf("%d",&input); des = (int*)malloc(sizeof(int)*input); if(NULL == des) { #ifdef DEBUG printf("[Error]:malloc failed! "); #endif return -1; } memset(des,0,sizeof(des)); div_num(input,des); #ifdef DEBUG printf(">>>>>>>>>>>> number div list <<<<<<<<<<<<< "); #endif for(i=0;i<g_point;i++) { printf("%d=%d+%d ",input,des[i],input-des[i]); } return 0; }
测试描述
注意事项
编译时,在Linux下注意编译选项要加-lm,即链接数学库。
上一篇:
Java基础知识总结(2021版)