Как можно оптимизировать решение данной задачи?

#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
 
//Primes() accepts certain number and returns and returns its expanded version(on primes) like vector.
 
vector<int> Primes(int n) {
    vector <int> v;
    while (n != 1) {
        for (int i = 2;; i++) {
            if (n % i == 0) {
                n /= i;
                v.push_back(i);
                break;
            }
        }
    }
    return v;
}
 
bool Factorial(int n) {
    //--------------------------------------------
    auto nPw = Primes(n*n); //now nPw contains all prime dividers of n^2
    //--------------------------------------------
    vector<int> values; values.reserve(n); //Vector values for storing all dividers of n!
    //--------------------------------------------
    for (int i = 1; i <= n; i++) {
        auto tmp = Primes(i);   //tmp stores all dividers of i
        move(tmp.begin(), tmp.end(), inserter(values, values.end()));   //moving tmp to the end of the values
    }
    //--------------------------------------------
    //Deleting all common dividers of n^2 and n!
    for(int i = 0; i != nPw.size(); i++){
        for(int j = 0; j != values.size(); j++){
            if (nPw[i] == values[j]) {
                nPw.erase(nPw.begin() + i);
                values.erase(values.begin() + j);
                i--; j--;
                break;
            }
        }
    }
    //--------------------------------------------
    return nPw.size() == 0;
}

#include <iostream>
 
typedef long long UINT;
 
bool foo(int n)
{   UINT r = 1;
    UINT nn = n * n;
    for(UINT i = 1; i < n; i++)
    {   r *= i;
        if(r%nn == 0) return true;
        r %= nn;
    }
    return false;
}
 
int main()
{   
    UINT start = 1000000000;
    for(UINT n = start; n < start + 30; n++)
    {   
        ///-----------------------------------|
        /// Ручной ввод.                      |
        ///-----------------------------------:
        /// std::cout << "n = "; std::cin >> n;
        
        std::cout << n << ":\t" << (foo(n) ? "TRUE" : "FALSE") << "\n";
    }
}

#include<iostream>
 
int main()
{
    unsigned long n;
    std::cin>>n;
    const unsigned long mod=n*n;
    unsigned long fact=1;
    for(unsigned long i=1;i<=n;++i)
        fact=(fact*i)%mod;
    std::cout<<(fact?"false":"true")<<std::endl;
    return 0;
}

bool foo(int n)
{   UINT r = 1;
    UINT nn = n * n;
    for(UINT i = 1; i <= n; i++)
    {   r *= i;
        r %= nn;
        if(r == 0) return true;
        
    }
    return false;
}

r = 1;
for(k=2; k<n; k++) {
  r = r*k%n;
  if (r==0) break;
}
if (r==0) cout << "Yes";
else cout << "No":