一个数分解成素数的乘积,放下代码,有兴趣的可以拿去耍耍
程序代码:
#include <math.h> #include <stdio.h> #include <stdlib.h> #define MAXPRIMENUM 100 static int primeroom[100]; int a[MAXPRIMENUM]; //生成素数函数 只有100个 void primenum_product() { int i,j=2,k=0,n=0; while(n<MAXPRIMENUM){ for(i=1;i<=j;i++){ if(j%i==0) k++; } if(k==2){ a[n]=j; n++; } j++; k=0; } } //用二分算法确定,给出的数值的平方根在上面生成素数的数组里的 位置确定 int sqrtnum_find(int sqrtnum,int n1,int n2 ) { int i=n2,n=(n1+n2)/2,j=n1; if(j-i>5){ if(sqrtnum<a[n]) sqrtnum_find(sqrtnum,n,i); else if(sqrtnum==a[n]){ return(n); exit(0); } else sqrtnum_find(sqrtnum,j,n); } else{ for(i;i<=j;i++) if(sqrtnum<=a[i]){ return(j); exit(0); } } } //将一个数分解成几个素数的乘积的算法,嘿嘿,不懂算法怎么走起的,请看离散数学第二章 void primenum_reduce(int interger,int n) { int sqrtnum,primenum=1,i=1,j,interger1; for(j=0;j<MAXPRIMENUM;j++){ if(interger==a[j]) { primeroom[n]=a[j]; i=0; } } if(i!=0){ sqrtnum=(int)sqrt(interger); if(sqrtnum>=1){ i=sqrtnum_find(sqrtnum,MAXPRIMENUM-1,0); for(j=0;j<i;j++){ if(interger%a[j]==0){ primenum*=a[j]; primeroom[n]=a[j]; n++; interger1=interger/a[j]; break; } } primenum_reduce(interger1,n); } } } void main() { int interger,i; primenum_product(); printf("请输入一个正整数:\n"); scanf("%d",&interger); primenum_reduce(interger,0); for(i=0;i<100;i++){ if(primeroom[i]!=0) printf("素数因子:%d\n",primeroom[i]); else break; } }
[ 本帖最后由 朱三哥 于 2013-1-21 12:04 编辑 ]