← Notes on Rieg Theory

Older Versions__OldVer__Programs.tex

\section{Programs}
\subsection{C++ code for modulo riegs}

\begin{shaded}
\begin{verbatim}
#include <bits/stdc++.h>
using namespace std;  
bool IsPrime(int p){
    if(p<2) return false;
    
    for(int i=2;i<p;i++){
        if(p%i == 0) return false;
    }
    return true;
}

int Rank(int n){
    if(n<=0) return -1;
    if(n==1) return 0;
    
    int p=2;
    while(n%p !=0) p++;
    
    int count =0;
    int m=n;
    while(m%p ==0){
        m=m/p;
        count++;
    } 
    return max(count, Rank(m));
}

int main() {
    int N;
    cin>>N;
    
    vector<bool> IsTame(N);
    for(int i=0;i<N;i++){
        IsTame.at(i) =true;
    }
    
    for(int p=2; p<N; p++){
        if (!IsPrime(p)) continue;
        for(int i=0;i<N;i++){
            if((i%p == 0) && (i%(p-1)!=0)) IsTame.at(i)=false;
        }
    }
    
    
    for(int a=0;a<5;a++){
        cout<<"a="<<a<<", b=";
        for(int b=1;b<N;b++){
             if(IsTame.at(b) && (Rank(b)<=a)) cout<<b<<", ";
        }
        cout<<endl;
    }
}
\end{verbatim}
\end{shaded}

\subsection{C++ code for rank of prime numbers}

\begin{shaded}
\begin{verbatim}
#include <bits/stdc++.h>
using namespace std;  

int ord(int p, int n){
    if(n%p!=0) return 0;
    else return ord(p,n/p)+1;
}

int main() {
    int N;
    cin>>N;
    
    vector<int> P(N);
    vector<int> D(N);
    for(int i=0;i<N;i++){
        P.at(i)=0;
        D.at(i)=1;
    }
    int k=0;
    int p=2;
    while(k<N){
        while(true){
            bool divided=false;
            for(int i=0;i<k;i++){
                if(p% P.at(i) == 0) divided=true;
            }
            if(divided) p++;
            else break;
        }
        P.at(k)=p;
        for(int i=0;i<k;i++){
            if((p-1)%P.at(i)==0){
                D.at(k) = max(D.at(k),D.at(i));
                D.at(k) = max(D.at(k),ord(P.at(i),p-1));
            }
        }
        k++;
        p++;
    }
    
    // for(int i=0;i<N;i++){
    //     cout<<P.at(i)<<" is degree "<<D.at(i)<<endl;
    // }
    
    // for(int i=0;i<N;i++){
    //     cout<<"d("<<P.at(i)<<")="<<D.at(i)<<",  ";
    // }
    
    for(int i=0;i<N;i++){
        if(D.at(i)<=2) cout<<P.at(i)<<", ";
    }
}
\end{verbatim}
\end{shaded}
\printbibliography

% \subsection{Data}
% \begin{align*}
%     \begin{autobreak}
%     \end{autobreak}
% \end{align*}