I am asking myself the following question:
Suppose one has a grid $G \in \mathbb{N}^{n\times n}$ where $g_{ij} = i\cdot j$, $i,j \leq n$. I would like to evaluate a function $f: G \to \mathbb{N}$.
Assuming the time to evaluate the function $f$ is really long, are there any way to reduce the time of computation?
For example I suppose the number of times the argument $g_{ij} = i\cdot j$ will be computed is the number of divisors of $i\cdot j$.
However, are there (fast) methods to determine if a number $x$ belongs to the multiplication grid $G$?
I am sorry if the question seems silly, I have to admit my basics in higher algebra and number theory are quite weak.
Thanks a lot for your answer!
So, you have a number $x$, $x\le n^2$, and you want to know whether $x=ij$ for some $1\le i,j\le n$.
There are pretty fast primality tests around (I'm sure you can find them by typing "primality test" into Google). If $x>n$ is prime, then you won't have $x=ij$. But if $x$ fails the primality test, you won't know whether it factors as a product of two numbers, each at most $n$. I don't think you can get that information without factoring $x$, and if it turns out $x$ has a lot of factors it may be hard to work out whether $x=ij$ with $1\le i,j\le n$.
Factoring $x$ is a lot harder than testing $x$ for primality. A lot depends on just how big the numbers you plan to deal with might be. If $n$ has 5 digits, a computer can solve the problem in a microsecond. If $n$ has 5000 digits, it might take the life of the Universe.