#include<iostream>
#include<vector>
#include<cmath>
#include<set>
using namespace std;

vector<int> fact(int n, int k, vector<int> factors){
     if(n==1){
        return factors;
    }
    else{
        if(n!=1){
            if(n%k==0){
            n = n/k;
            factors.push_back(k);
            return fact(n, k, factors);
        }
        else{
            k++;
            return fact(n, k, factors);
        }
    }
    }
}

int fi(int n, int k, int phi, int exp, vector<int> factors){
    if(n==1){
        for(int i=1; i<exp; i++){
                phi = phi*k;
            }
        if(exp!=0){
                phi = phi*(k-1);
            }
        return phi;
    }
    else{
        if(n!=1){
            if(n%k==0){
            n = n/k;
            factors.push_back(k);
            exp++;
            return fi(n, k, phi, exp, factors);
        }
        else{
            for(int i=1; i<exp; i++){
                phi = phi*k;
            }
            if(exp!=0){
                phi = phi*(k-1);
            }
            k++;
            return fi(n, k, phi, 0, factors);
        }
    }
    }
}

int main(){
    cout<<"Introduce until what number: ";
    int mm;
    cin>>mm;
    int m = mm+1;
    for(int n=1; n<m; n++){
        int primer = 0;
        for(int t=2; t*t<=n; t++){
            if(n%t==0){
                primer = 1;
                break;
            }
        }
        if(primer==0){
             int res;
        int comp = 0;
        int cot = 0;
        vector<int> factors;
        int euler = fi(n, 2, 1, 0, factors);
        factors = fact(euler, 2, factors);
        for(int i=1; i<n; i++){
                 comp = 0;
            for(int j=0; j<factors.size(); j++){
                    res = 1;
                for(int q=1; q<=(euler/factors[j]); q++){
                    res = (res*i)%n;
                }
            if(res==1){
                comp = 1;
                break;
            }
            }
            if((cot==0)and(comp==0)){
                cout<<endl<<"number: "<<n<<endl;
                cot++;
            }
            if(comp==0){
                cout<<i<<"   ";

            }
        }
        }
        if(primer==1){
            int cot = 0;
            for(int i=1; i<n; i++){
                set<int> s;
            for(int j=1; j<n; j++){
                    int res = 1;
                for(int q=0; q<j; q++){
                    res = (res*i)%n;
                }
            int fal = 0;
            for(int y=2; y<=i; y++){
                if((n%y==0)and(i%y==0)){
                    fal = 1;
                }
            }
            if(fal==0){
                s.insert(res);
            }
            }
            vector<int> factors;
            int euler = fi(n, 2, 1, 0, factors);
            if((s.size()==euler) and (cot==0)){
                cout<<endl<<"number: "<<n<<endl;
                cot++;
            }
            if((s.size()==euler)and(cot!=0)){
               cout<<i<<"   ";
            }
        }

    }
}
}