Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I want to compute $ A= \langle \text{GCD}(a,j),j=2,3,..,k-1\rangle$ and assume that each value of $j$ is less than $a$. I can compute GCD(a,j), $j=2,3,..,k-1$ and $a \le j$ for single fixed value of $j$ in $\Omega(\log j)$ airthmetic operations.
Easily we can compute set $A$ in $O(k \log k )$ airthmetic operations.
Question : How to compute set $A$ in $O(k)$ many arithmetic operations?
Using a linear sieve like this:
https://e-maxx-eng.appspot.com/algebra/prime-sieve-linear.html
you can factor every number in range $j=2,3,..,k-1$ in linear time.
From there, you get an array with some prime divisor (the least for example) of each number in the range. Using that you can solve your problem by filling $A$ in order, and for each new number $j$ you just use the prime divisor of it, find it's greater exponent in $a$, and $j$, and use the previously calculated results in $A$ to get your answer. I'm not totally sure this last part it runs in linear time, but it should be possible.
