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?

  • 2
    $\begingroup$ Is this homework? $\endgroup$ Jan 25, 2018 at 20:51
  • $\begingroup$ @ Emil Jeřábek No I am currently reading a research paper (finite abelian group isomorphism in linear time) in which they have claimed this result. $\endgroup$
    – new
    Jan 26, 2018 at 4:26

1 Answer 1


Using a linear sieve like this:


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.

  • $\begingroup$ It sounds like you’re saying factoring can be done in linear time. That’s not (known to be) true, so I’m having trouble understanding what you’re going for here $\endgroup$ Jan 25, 2018 at 23:42
  • 1
    $\begingroup$ Reynaldo is saying that all integers from $2$ to $n$ can be labeled with their smallest prime divisor in time $O(n)$ using a simple sieving algorithm. This is quite different from factoring a given integer in time linear in its bit size. $\endgroup$ Jan 26, 2018 at 1:40
  • $\begingroup$ You don't need to bother with exponents. If p[j]$l is the array of prime divisors of the j's: `A[1]:=1; for j=2..k-1 do { if (A[j/p[j]]*p[j] divides j and a) then A[j]:=A[j/p[j]]*p[j] else A[j]:=A[j/p[j]] }. This is clearly linear time. $\endgroup$ Jan 26, 2018 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.