<p>Using a linear sieve like this:</p>

<p><a href="https://e-maxx-eng.appspot.com/algebra/prime-sieve-linear.html" rel="nofollow noreferrer">https://e-maxx-eng.appspot.com/algebra/prime-sieve-linear.html</a></p>

<p>you can factor every number in range $j=2,3,..,k-1$ in linear time.</p>

<p>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.</p>

CC BY-SA 3.0
2018-01-25T23:42:47.047Z
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
Stella Biderman
CC BY-SA 3.0
2018-01-26T01:40:29.583Z
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.
Sasho Nikolov
CC BY-SA 3.0
2018-01-26T10:00:52.540Z
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.
Emil Jeřábek
CC BY-SA 3.0
2018-01-25T21:28:57.443Z
2018-01-25T21:28:57.443Z
gilcu3
<p>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.</p>

<p>Easily we can compute set $A$ in $O(k \log k )$ airthmetic operations.</p>

<p><strong>Question :</strong> How to compute set $A$ in $O(k)$ many arithmetic operations?</p>

CC BY-SA 3.0
2018-01-25T20:51:46.027Z
Is this homework?
Emil Jeřábek
CC BY-SA 3.0
2018-01-26T04:26:44.077Z
@ 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.
new
<cc.complexity-theory><ds.algorithms>
How to compute GCD efficiently?
new
# How to compute GCD efficiently?

(Asked by: username_0 on 2018-01-25)

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?

**Tags:** cc.complexity-theory, ds.algorithms

> **Comments:**
> **username_1**: Is this homework?  
> **username_0**: @ username_1 No I am currently reading a research paper (finite abelian group isomorphism in linear time) in which they have claimed this result.  

---

## 1 answers

### Answer by username_2 on 2018-01-25. Score: 3

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 username_0 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.

> **Comments:**
> **username_3**: 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  
> **username_4**: 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.  
> **username_1**: 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.  

---

