#include<iostream>
#include<vector>
#include<cmath>
#include<set>

using namespace std;

vector <bool> v;
vector <int> primers;
vector <vector <int> > factors;
vector <vector <int> > factorsrepet;

void garbell(){
    v[0]=false;
    v[1]=false;
    for(int i=2; i<v.size(); i++){
        if(v[i]){
            primers.push_back(i);
            for(int h=2; h*i<v.size(); h++){
                v[i*h] = 0;
                factors[i*h].push_back(i);
                int repet = i*h;
                while(repet%i==0){
                    repet = repet/i;
                    factorsrepet[i*h].push_back(i);
                }
            }
        }
    }
}

int main(){
    int n;
    cout<<"Introduce until what number: ";
    cin >> n;
    int utot = 0;
    int dostot = 0;
    int trestot = 0;
    int quatretot = 0;
    int cinctot = 0;
    int sistot = 0;
    v = vector <bool> (n, true);
    primers = vector <int> ();
    factors = vector <vector <int>> (n);
    factorsrepet = vector <vector <int>> (n);
    garbell();
    //cout<<"numero: "<<2<<endl<<1<<endl;
    trestot++;  //canvi-ho si canvies els intervals
    //cout<<"numero: "<<4<<endl<<3<<endl;
    quatretot++;  //lomateix
    for(int i=1; i<primers.size(); i++){
        int pot = primers[i];
        int k = 1;
        for(int q=1; q<k; q++){
                pot = pot*pot;
            }
        while(pot<=n){
            //cout<<endl<<"numero: "<<pot;
            if(k==1){
                //cout<<endl;
                int euler=pot-1;
            for (int arr=2; arr<pot; arr++){
                int comp=0;
                for(int s=0; s<factors[euler].size(); s++){
                    int res = 1;
                    for(int m=1; m<=(euler/factors[euler][s]); m++){
                        res = (res*arr)%pot;
                    }
                    if(res==1){
                        comp = 1;
                        break;
                    }
                }
                    if(comp==0){
                      //cout<<arr<<"   ";
                       double s = pot;
                       float nn = s/3;
                        if(arr <= nn){
                            utot++;
                        }
                        if((arr > nn)and(arr <=nn*2)){
                            dostot++;
                        }
                        if((arr > nn*2)and(arr <= n)){
                            trestot++;
                        }
                    }
            }
            if(2*pot<=n){
                //cout<<endl;
                int dospot = 2*pot;
                //cout<<"numero: "<<dospot<<endl;
                int euler = primers[i]-1;
                for(int q=1; q<k; q++){
                    euler = euler*primers[i];
                }
                int cot = 0;
                for(int i=2; i<dospot; i++){
                    set<int> s;
                    for(int j=1; j<dospot; j++){
                            int res = 1;
                        for(int q=0; q<j; q++){
                            res = (res*i)%(dospot);
                        }
                    int fal = 0;
                    for(int y=2; y<=i; y++){
                        if(((dospot)%y==0)and(i%y==0)){
                            fal = 1;
                        }
                    }
                    if(fal==0){
                        s.insert(res);
                    }
                    }
                    if((s.size()==euler)){
                        //cout<<i<<"   ";
                        double s = dospot;
                       float nn = s/3;
                        if(i <= nn){
                            utot++;
                        }
                        if((i > nn)and(i <=nn*2)){
                            dostot++;
                        }
                        if((i > nn*2)and(i <= n)){
                            trestot++;
                        }
                    }
            }
        }
            }
            if(k!=1){
                //cout<<endl;
                int euler = primers[i]-1;
                for(int q=1; q<k; q++){
                    euler = euler*primers[i];
                }
                int cot = 0;
                for(int i=2; i<pot; i++){
                    set<int> s;
                    for(int j=1; j<pot; j++){
                            int res = 1;
                        for(int q=0; q<j; q++){
                            res = (res*i)%pot;
                        }
                    int fal = 0;
                    for(int y=2; y<=i; y++){
                        if((pot%y==0)and(i%y==0)){
                            fal = 1;
                        }
                    }
                    if(fal==0){
                        s.insert(res);
                    }
                    }
                    if((s.size()==euler)){
                        //cout<<i<<"   ";
                        double s = pot;
                       float nn = s/3;
                        if(i <= nn){
                            utot++;
                        }
                        if((i > nn)and(i <=nn*2)){
                            dostot++;
                        }
                        if((i > nn*2)and(i <= n)){
                            trestot++;
                        }
                    }
           }
            if(2*pot<=n){
                //cout<<endl;
                int dospot = 2*pot;
                //cout<<"numero: "<<dospot<<endl;
                int euler = primers[i]-1;
                for(int q=1; q<k; q++){
                    euler = euler*primers[i];
                }
                int cot = 0;
                for(int i=2; i<dospot; i++){
                    set<int> s;
                    for(int j=1; j<dospot; j++){
                            int res = 1;
                        for(int q=0; q<j; q++){
                            res = (res*i)%(dospot);
                        }
                    int fal = 0;
                    for(int y=2; y<=i; y++){
                        if(((dospot)%y==0)and(i%y==0)){
                            fal = 1;
                        }
                    }
                    if(fal==0){
                        s.insert(res);
                    }
                    }
                    if((s.size()==euler)){
                        //cout<<i<<"   ";
                        double s = dospot;
                       float nn = s/3;
                        if(i <= nn){
                            utot++;
                        }
                        if((i > nn)and(i <=nn*2)){
                            dostot++;
                        }
                        if((i > nn*2)and(i <= n)){
                            trestot++;
                        }
                        }
            }
        }
    }
            k++;
            for(int q=1; q<k; q++){
                pot = pot*pot;
            }
        }
    }
    cout<<endl<<"interval 1: "<<utot<<endl;
    cout<<endl<<"interval 2: "<<dostot<<endl;
    cout<<endl<<"interval 3: "<<trestot<<endl;
}