Filling the prefix array following relation prefix ( i ) = GCD ( prefix ( i - 1 ) , arr ( i ) )
$ prefix [ 0 ] = $ arr [ 0 ] ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) $ prefix [ $ i ] = GCD ( $ prefix [ $ i - 1 ] , $ arr [ $ i ] ) ;