#include "mod/primes.h"
#include "mod/modarith.h"

#include "ds/bitarray.h"

#include "mod/factor.h"
#include "demo/nextarg.h"
#include "fxttypes.h"  // ulong


//% Find moduli where all quadratic (or higher) residues are non-prime.

// cf.: A065428 Numbers n such that all x^2 mod n are nonprimes.


int
main(int argc, char **argv)
{
    ulong n = 2000;
    NXARG(n,"Search limit for moduli");
    bitarray *ba = make_oddprime_bitarray(n);
    ulong e = 2;
    NXARG(e,"Exponent (2==>squares, 3==>cubes, ...)");

    ulong ct = 0;
    for ( umod_t m=2; m<n; ++m)
    {
        bool q = 0;
        for ( umod_t x=0; x<m; ++x )
        {
            umod_t z = pow_mod(x, e, m);
            q |= is_small_prime( z, ba );
        }

        if ( 0==q )
        {
            factorization fm(m);
            ++ct;
            cout << m;
            cout << " == " << fm;
            cout << endl;
        }
    }

    cout << endl;
    cout << " #=" << ct << endl;

    delete ba;

    return 0;
}
// -------------------------

/// Emacs:
/// Local Variables:
/// MyRelDir: "demo/mod"
/// makefile-dir: "../../"
/// make-target: "1demo DSRC=demo/mod/mod-residues-demo.cc"
/// make-target2: "1demo DSRC=demo/mod/mod-residues-demo.cc DEMOFLAGS=-DTIMING"
/// End: