【数論内容】線形ふるい素数、線形ふるいオーラ関数、前のN個数の約数を求める
11134 ワード
【数論内容】線形ふるい素数、線形ふるいオーラ関数、前のN個数の約数を求める
まず最も基本的な線形ふるいの素数に来て、後のアルゴリズムは実はすべてこの最も基本的なアルゴリズムに基づいています:
1 #include<stdio.h>
2 #include<string.h>
3 #define M 10000000
4 int prime[M/3];
5 bool flag[M];
6 void get_prime()
7 {
8 int i,j,k;
9 memset(flag,false,sizeof(flag));
10 k=0;
11 for(i=2;i<M;i++){
12 if(!flag[i])
13 prime[k++]=i;
14 for(j=0;j<k&&i*prime[j]<M;j++){
15 flag[i*prime[j]]=true;
16 if(i%prime[j]==0)
17 break;
18 }
19 }
20 }
21 int main()
22 {}各合数には必ず最小素因子があり、各合数はその最小素因子によってちょうど1回スクリーニングされるので、線形時間である.コードにはif(i%prime[j]=0)break;--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------私は控えめな分割線です----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------(2)もし(N%a==0&&(N/a)%a!=0)は、E(N)=E(N/a)*(a-1);ここでaはNの素因数である.Euler関数については,(1)phi[p]=p−1;(pは素数);(2)N=p^n(pが素数)であればphi[N]=(p-1)*p^(n-1);オラ関数についてはWikiで詳しく紹介されています.
1 #include<stdio.h>
2 #include<string.h>
3 #define M 10000000
4 int prime[M/3],phi[M];
5 bool flag[M];
6 void get_prime()
7 {
8 int i,j,k;
9 memset(flag,false,sizeof(flag));
10 k=0;
11 for(i=2;i<M;i++){
12 if(!flag[i]){
13 prime[k++]=i;
14 phi[i]=i-1;
15 }
16 for(j=0;j<k&&i*prime[j]<M;j++){
17 flag[i*prime[j]]=true;
18 if(i%prime[j]==0){
19 phi[i*prime[j]]=phi[i]*prime[j];
20 break;
21 }
22 else
23 phi[i*prime[j]]=phi[i]*(prime[j]-1);
24 }
25 }
26 }
27 int main()
28 {}-------------------------------------------------------------------------------------------------------------------
数を数えるのは少し複雑ですが、大体その意味です.
約数の性質は、1つの数Nに対して、N=p 1^a 1+p 2^a 2+...+pn^an.そのうちp 1,p 2,p 3...pnはNの素因数,a 1,a 2,a 2,...anが対応する指数であれば
div_num[N]=(p1+1)*(p2+1)*(p3+1)* ... *(pn+1);
このアルゴリズムの特徴と結びつけて、プログラムの中で以下のように運用します.
div_の場合num:
(1)i|prime[j]の場合div_num[i*prime[j]]=div_sum[i]/(e[i]+1)*(e[i]+2)/最小素因子回数プラス1
(2)そうでない場合div_num[i*prime[j]]=div_num[i]*div_num[prime[j]//積性関数条件を満たす
eの場合:
(1)i|pr[j]e[i*pr[j]=e[i]+1;最小素因数回数プラス1
(2)そうでなければe[i*pr[j]=1;//pr[j]は1回
1 #include<stdio.h>
2 #include<string.h>
3 #define M 10000000
4 int prime[M/3],e[M/3],div_num[M]; // e[i] i
5 bool flag[M];
6 void get_prime()
7 {
8 int i,j,k;
9 memset(flag,false,sizeof(flag));
10 k=0;
11 for(i=2;i<M;i++){
12 if(!flag[i]){
13 prime[k++]=i;
14 e[i]=1;
15 div_num[i]=2; // 2
16 }
17 for(j=0;j<k&&i*prime[j]<M;j++){
18 flag[i*prime[j]]=true;
19 if(i%prime[j]==0){
20 div_num[i*prime[j]]=div_num[i]/(e[i]+1)*(e[i]+2);
21 e[i*prime[j]]=e[i]+1;
22 break;
23 }
24 else{
25 div_num[i*prime[j]]=div_num[i]*div_num[prime[j]];
26 e[i]=1;
27 }
28 }
29 }
30 }
31 int main()
32 {}
33
34
35 みんなに収穫があることを望みます~~
Made by M.J