package main

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

const MAXA = 5000005

var phi [MAXA]int32
var depth [MAXA]int8
var primes = make([]int32, 0, 348514)

func initSieve() {
	phi[1] = 1
	depth[1] = 0
	for i := int32(2); i < MAXA; i++ {
		if phi[i] == 0 {
			primes = append(primes, i)
			phi[i] = i - 1
		}
		for _, p := range primes {
			if i*p >= MAXA {
				break
			}
			if i%p == 0 {
				phi[i*p] = phi[i] * p
				break
			} else {
				phi[i*p] = phi[i] * (p - 1)
			}
		}
	}
	for i := int32(2); i < MAXA; i++ {
		depth[i] = depth[phi[i]] + 1
	}
}

func readInt(r *bufio.Reader) int {
	var n int
	var c byte
	var err error
	for {
		c, err = r.ReadByte()
		if err != nil {
			return 0
		}
		if c >= '0' && c <= '9' {
			break
		}
	}
	for {
		n = n*10 + int(c-'0')
		c, err = r.ReadByte()
		if err != nil || c < '0' || c > '9' {
			break
		}
	}
	return n
}

func get_lca(u, v int32) int32 {
	if u == 0 {
		return v
	}
	if v == 0 {
		return u
	}
	for u != v {
		if depth[u] < depth[v] {
			v = phi[v]
		} else if depth[u] > depth[v] {
			u = phi[u]
		} else {
			u = phi[u]
			v = phi[v]
		}
	}
	return u
}

var sum_depth []int64
var lca []int32

func pushUp(idx int) {
	sum_depth[idx] = sum_depth[idx<<1] + sum_depth[idx<<1|1]
	lca[idx] = get_lca(lca[idx<<1], lca[idx<<1|1])
}

func build(idx, l, r int, reader *bufio.Reader) {
	if l == r {
		val := int32(readInt(reader))
		lca[idx] = val
		sum_depth[idx] = int64(depth[val])
		return
	}
	mid := (l + r) >> 1
	build(idx<<1, l, mid, reader)
	build(idx<<1|1, mid+1, r, reader)
	pushUp(idx)
}

func update(idx, l, r, ql, qr int) {
	if sum_depth[idx] == 0 {
		return
	}
	if l == r {
		lca[idx] = phi[lca[idx]]
		sum_depth[idx] = int64(depth[lca[idx]])
		return
	}
	mid := (l + r) >> 1
	if ql <= mid {
		update(idx<<1, l, mid, ql, qr)
	}
	if qr > mid {
		update(idx<<1|1, mid+1, r, ql, qr)
	}
	pushUp(idx)
}

func query(idx, l, r, ql, qr int) (int64, int32) {
	if ql <= l && r <= qr {
		return sum_depth[idx], lca[idx]
	}
	mid := (l + r) >> 1
	var sd1, sd2 int64
	var lca1, lca2 int32
	if ql <= mid {
		sd1, lca1 = query(idx<<1, l, mid, ql, qr)
	}
	if qr > mid {
		sd2, lca2 = query(idx<<1|1, mid+1, r, ql, qr)
	}
	return sd1 + sd2, get_lca(lca1, lca2)
}

func main() {
	initSieve()
	reader := bufio.NewReaderSize(os.Stdin, 65536)
	writer := bufio.NewWriterSize(os.Stdout, 65536)
	defer writer.Flush()

	n := readInt(reader)
	if n == 0 {
		return
	}
	m := readInt(reader)

	sum_depth = make([]int64, 4*n+1)
	lca = make([]int32, 4*n+1)

	build(1, 1, n, reader)

	for i := 0; i < m; i++ {
		t := readInt(reader)
		l := readInt(reader)
		r := readInt(reader)
		if t == 1 {
			update(1, 1, n, l, r)
		} else {
			sd, lc := query(1, 1, n, l, r)
			ans := sd - int64(r-l+1)*int64(depth[lc])
			fmt.Fprintln(writer, ans)
		}
	}
}