可以分解2^64-1内的数,速度很快,傻瓜级代码,就不做注释了
代码:
#include <stdio.h> #include <windows.h> const unsigned __int64 prime[2] = {2,3}; const int primeNumTblSize = sizeof(prime) / sizeof(prime[0]); void PrintFactorization( unsigned __int64 srcNum, unsigned __int64 baseNum ) { unsigned __int64 yinzi[64] = {0}; int mi[64] = {0}; int numOfYinzi = 0; if (srcNum == 1 || srcNum == 0) printf("is neither a prime number nor a composite number\n**************************************************\n", srcNum); else if (srcNum < 4) printf("is a prime number.\n**************************************************\n"); else { while (srcNum > 1) { for (int i = 0; i < primeNumTblSize; i++) { if (srcNum % prime[i] == 0) { if (numOfYinzi == 0) { yinzi[0] = prime[i]; mi[0]++; numOfYinzi++; } else { if (yinzi[numOfYinzi-1] == prime[i]) mi[numOfYinzi-1]++; else { yinzi[numOfYinzi] = prime[i]; mi[numOfYinzi]++; numOfYinzi++; } } srcNum /= prime[i]; break; } } if (i >= primeNumTblSize) { for (baseNum; baseNum * baseNum <= srcNum; baseNum += 6) { if (srcNum % baseNum == 0) { if (numOfYinzi == 0) { yinzi[0] = baseNum; mi[0]++; numOfYinzi++; } else { if (yinzi[numOfYinzi-1] == baseNum) mi[numOfYinzi-1]++; else { yinzi[numOfYinzi] = baseNum; mi[numOfYinzi]++; numOfYinzi++; } } srcNum /= baseNum; break; } else if (srcNum % (baseNum + 2) == 0) { if (numOfYinzi == 0) { yinzi[0] = (baseNum + 2); mi[0]++; numOfYinzi++; } else { if (yinzi[numOfYinzi-1] == (baseNum + 2)) mi[numOfYinzi-1]++; else { yinzi[numOfYinzi] = (baseNum + 2); mi[numOfYinzi]++; numOfYinzi++; } } srcNum /= (baseNum + 2); break; } } if (baseNum * baseNum > srcNum) { if (numOfYinzi == 0) { yinzi[0] = srcNum; mi[0]++; numOfYinzi++; } else { if (yinzi[numOfYinzi-1] == srcNum) mi[numOfYinzi-1]++; else { yinzi[numOfYinzi] = srcNum; mi[numOfYinzi]++; numOfYinzi++; } } srcNum = 1; } } } if (numOfYinzi == 1 && mi[0] == 1) printf("is a prime number.\n**************************************************\n"); else { printf("= "); for (int ww = 0; ww < numOfYinzi-1; ww++) { if (yinzi[ww] != 0) mi[ww] == 1 ? printf("%I64u x ", yinzi[ww]) : printf("%I64u^%d x ", yinzi[ww], mi[ww]); } mi[numOfYinzi-1] == 1 ? printf("%I64u\n", yinzi[numOfYinzi-1]) : printf("%I64u^%d\n", yinzi[numOfYinzi-1], mi[numOfYinzi-1]); printf("**************************************************\n"); } } } int main(int argc,char *argv[]) { system("title Factorization v1.1 -- DevilHand Presents"); unsigned __int64 srcNum = 0; unsigned __int64 baseNum = 5; int scanfRet = 0; int suanfa = 2; printf("**************************************************\n"); printf(" * Factorization v1.1\n"); printf(" * DevilHand Presents 2011-03-18\n"); printf(" * Email: DevilHand@126.com\n"); printf("**************************************************\n"); while (1) { srcNum = 0; do { fflush(stdin); printf("Input a number: "); scanfRet = scanf("%I64u", &srcNum); } while (EOF == scanfRet || 0 == scanfRet); printf("Result: %I64u ", srcNum); PrintFactorization(srcNum, baseNum); } return 0; }