```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

const MAX = 1000005

var D = make([]int, MAX)

func precomputeD() {
	for i := 1; i < MAX; i++ {
		for j := i; j < MAX; j += i {
			D[j]++
		}
	}
}

func findMaxL() int {
	maxL := 0
	for i := 1; i < MAX; i++ {
		cur := i
		steps := 0
		for {
			next := D[cur]
			if next == cur {
				break
			}
			cur = next
			steps++
			if steps > maxL {
				maxL = steps
			}
		}
	}
	return maxL
}

type Block struct {
	start, size int
	vals        []int
	sumAfter    []int64
	lazy        int
}

func (b *Block) recompute() {
	for i := 0; i <= L; i++ {
		b.sumAfter[i] = 0
	}
	for j := 0; j < b.size; j++ {
		cur := b.vals[j]
		for m := 0; m <= L; m++ {
			b.sumAfter[m] += int64(cur)
			cur = D[cur]
		}
	}
}

func (b *Block) push() {
	if b.lazy == 0 {
		return
	}
	for j := 0; j < b.size; j++ {
		cur := b.vals[j]
		for t := 0; t < b.lazy; t++ {
			next := D[cur]
			if next == cur {
				break
			}
			cur = next
		}
		b.vals[j] = cur
	}
	b.lazy = 0
}

var B = 128
var L int

func computeSum(l, r int, blocks []Block) int64 {
	var ans int64 = 0
	lblock := (l - 1) / B
	rblock := (r - 1) / B
	if lblock == rblock {
		bb := blocks[lblock]
		posL := l - bb.start
		posR := r - bb.start
		for j := posL; j <= posR; j++ {
			cur := bb.vals[j]
			lt := bb.lazy
			for t := 0; t < lt; t++ {
				next := D[cur]
				if next == cur {
					break
				}
				cur = next
			}
			ans += int64(cur)
		}
	} else {
		bb := blocks[lblock]
		posL := l - bb.start
		posR := bb.size - 1
		for j := posL; j <= posR && j < bb.size; j++ {
			cur := bb.vals[j]
			lt := bb.lazy
			for t := 0; t < lt; t++ {
				next := D[cur]
				if next == cur {
					break
				}
				cur = next
			}
			ans += int64(cur)
		}
		bb = blocks[rblock]
		posL = 0
		posR = r - bb.start
		for j := posL; j <= posR; j++ {
			cur := bb.vals[j]
			lt := bb.lazy
			for t := 0; t < lt; t++ {
				next := D[cur]
				if next == cur {
					break
				}
				cur = next
			}
			ans += int64(cur)
		}
		for id := lblock + 1; id < rblock; id++ {
			bb := blocks[id]
			mm := bb.lazy
			if mm > L {
				mm = L
			}
			ans += bb.sumAfter[mm]
		}
	}
	return ans
}

func doReplace(l, r int, blocks []Block) {
	lblock := (l - 1) / B
	rblock := (r - 1) / B
	if lblock == rblock {
		bb := &blocks[lblock]
		bb.push()
		posL := l - bb.start
		posR := r - bb.start
		for j := posL; j <= posR && j < bb.size; j++ {
			bb.vals[j] = D[bb.vals[j]]
		}
		bb.recompute()
	} else {
		bb := &blocks[lblock]
		bb.push()
		posL := l - bb.start
		posR := bb.size - 1
		for j := posL; j <= posR && j < bb.size; j++ {
			bb.vals[j] = D[bb.vals[j]]
		}
		bb.recompute()
		bb = &blocks[rblock]
		bb.push()
		posL = 0
		posR = r - bb.start
		for j := posL; j <= posR; j++ {
			bb.vals[j] = D[bb.vals[j]]
		}
		bb.recompute()
		for id := lblock + 1; id < rblock; id++ {
			if blocks[id].lazy < L {
				blocks[id].lazy++
			}
		}
	}
}

func main() {
	precomputeD()
	L = findMaxL()
	reader := bufio.NewReader(os.Stdin)
	nextInt := func() int {
		var x int
		fmt.Fscan(reader, &x)
		return x
	}
	n := nextInt()
	m := nextInt()
	a := make([]int, n+1)
	for i := 1; i <= n; i++ {
		a[i] = nextInt()
	}
	numBlocks := (n + B - 1) / B
	blocks := make([]Block, numBlocks)
	for id := 0; id < numBlocks; id++ {
		start := id*B + 1
		end := start + B - 1
		if end > n {
			end = n
		}
		size := end - start + 1
		vals := make([]int, size)
		for j := 0; j < size; j++ {
			vals[j] = a[start+j]
		}
		sumAfter := make([]int64, L+1)
		blocks[id] = Block{start: start, size: size, vals: vals, sumAfter: sumAfter, lazy: 0}
		blocks[id].recompute()
	}
	var answers []int64
	for q := 0; q < m; q++ {
		ti := nextInt()
		l := nextInt()
		r := nextInt()
		if ti == 2 {
			ans := computeSum(l, r, blocks)
			answers = append(answers, ans)
		} else {
			doReplace(l, r, blocks)
		}
	}
	writer := bufio.NewWriter(os.Stdout)
	for _, ans := range answers {
		fmt.Fprintln(writer, ans)
	}
	writer.Flush()
}
```