小議素數(shù)序列求法以及使用
昨天想學(xué)習(xí)下python，在qq上找到了一個群，結(jié)果發(fā)現(xiàn)加群的問題是，求群號的平方的約數(shù)和。頓覺頭大。上網(wǎng)查了下資料，現(xiàn)在給出C++代碼如下
算法目的：
求給定任意一個int型整數(shù)的約數(shù)個數(shù)
算法過程：
根據(jù)威爾遜定理（公式顯示不出來。。。）的遞推過程，素數(shù)2出現(xiàn)無限多次，其余的素數(shù)恰好出現(xiàn)一次。
?
先求出該數(shù)的10的對數(shù)，然后使用威爾遜定理計算1-10? 11-100?? 101-1000……n+1—n*10之間的素數(shù)序列；每求出一個素數(shù)序列，就用它們除原數(shù)，這樣可以逐漸減少運算規(guī)模。
???????? 之所以這樣做，根據(jù)是絕大多數(shù)情況下，我們所列的數(shù)，其約數(shù)都是由比較小的質(zhì)數(shù)組合而成，這是大多數(shù)情況，在極少數(shù)情況下，給的數(shù)是剛好是很大的質(zhì)數(shù)，或者其約數(shù)很大；另外，威爾遜序列需要數(shù)的階乘，符合迭代關(guān)系。
?
???????? 其中，素數(shù)序列的求法沒有什么可以稱得上好的方法，威爾遜定理的缺陷在于要計算數(shù)的階乘。如果給定的數(shù)是一個很大的素數(shù)，那么該算法幾乎沒什么效率。當然，數(shù)的溢出也在所難免了。畢竟long的表示范圍也是有限的
?
使用C++ 實現(xiàn)，代碼稍加修改，可以解決與素數(shù)序列有關(guān)的問題，某些地方空格粘貼不出來，我可能沒有檢查完，所以直接粘貼可能運行不了，但是這種問題應(yīng)該都比較明顯，另外代碼有很大的改進空間，感興趣的話可以多提提意見，互相學(xué)習(xí)
頭文件
?
#include
#include
using namespace std;
?
typedef struct?tag_divisor
{
??? intddivisor;
??? intdexponent;
??? tag_divisor(intdivisor,int exponent)
??? {
??????? ddivisor = divisor;
??????? dexponent = exponent;
??? }
}Divisor;
?
class DC
{
??? //divisorcalculate
??? private:
??????????? //使用威爾遜定理計算素數(shù)序列
??? ??????? void calPrime(long&tmp,int num1,int?num2,vector
??? public:
??????????? //計算約數(shù)個數(shù)
??????? int?calDC(int num);
};
?
資源文件
?
#include "Simple1.h"
#include
?
int DC::calDC(intnum)
{
??? int temp =num;
??? int log_10 =log10((double)temp);
??? long?factorial = 1;
???
??? vector
??? v.push_back(Divisor(2,0));
??? int j =0;? //當前素數(shù)序列的索引
??? for (int i = 10; i < temp; i*=10)
??? {
??????? calPrime(factorial,i/10,i,v);
??????? for (;j< v.size();j++)
??????? {
??????????? Divisor &d = v[j];
??????????? while(temp%d.ddivisor== 0)
??????????? {
??????????????? temp = temp/d.ddivisor;
??????????????? d.dexponent++;
??????????? }
??????? }
??? }
?
??? int count =1;
??? for (int k = 0; k < v.size();k++)
??? {
??????? Divisor &d = v[k];
??????? count *= d.dexponent+1;
??? }
??? v.swap(vector
?
??? return?count;
}
?
void DC::calPrime(long&tmp,int num1,intnum2,vector
{
??? for (long i = num1 + 1; i<=num2; i++)
??? {
??????? tmp*=i;
??????? longwilson = (tmp*2)%(i+1)+2;
??????? if(wilson != 2)
??????? {
??????????? v.push_back(Divisor(wilson,0));
??????? }
??? }
}
在visual studio 上運行，初步未檢測到錯誤，歡迎大家拍磚
下載文檔
