Use sieve to keep track of prime factorization of numbers to . Then for all primes, keep track of the indices that have their multiples. Then for sum and querying you can use a segment tree. And to update, use the multiple list to only update those values that have gcd > 1. A number will be updated at most times, so the solution is