主題
題目連結：
題目意譯：
你被給定一個索引值從 0 開始且長度為 n 的整數陣列 nums。
一個位於索引值 i（其中 0 ≦ i ≦ n - 2）的「分割」如果滿足前 i + 1 個元素之乘積與剩餘元素之乘積是互質的話，則該分割視為合法。
例如說，如果 nums = [2, 3, 3]，則位於索引值 i = 0 的分割是合法的，因為 2 和 9 互質；而位於索引值 i = 1 的分割則不合法，因為 6 和 3 不互質。同時位於 i = 2 的分割不合法，因為 i == n - 1。
回傳最小的索引值 i 使得對應分割合法。如果不存在著這樣子的分割，則回傳 -1。
兩個數值 val1 和 val2 如果滿足 gcd(val1, val2) == 1 的話，則兩數互質。其中 gcd(val1, val2) 是 val1 和 val2 的最大公因數（Greatest Common Divisor）。
限制：
n == nums.length
1 ≦ n ≦ 10 ^ 4
1 ≦ nums[i] ≦ 10 ^ 6
範例測資：
範例 1：
輸入： nums = [4,7,8,15,3,5]
輸出： 2
解釋： 上列表格表示了位於索引值 i 時的前 i + 1 個元素的乘積值、剩餘元素的乘積值以及它們的最大公因數。
唯一合法的分割是在索引值 2 出現。
範例 2：
輸入： nums = [4,7,15,8,3,5]
輸出： -1
解釋： 上列表格表示了位於索引值 i 時的前 i + 1 個元素的乘積值、剩餘元素的乘積值以及它們的最大公因數。
此例不存在合法分割。
解題思維：
可以看到直接算前綴和後綴的乘積會需要大數乘法（所以可能 Python 會比較吃香？這部分我不知道。我的直覺是依舊會超時），而這不甚理想。
不過因為題目要的是「互質」，因此我們可以改存前綴和後綴的各自質因數之次方值（如果不互質，代表存在著某個質因數，使得兩者的次方值都大於 0）。因此我們需要先建立質數表還有把數字質因數分解的方法，參見這題。
定義 P[i] 為前 i + 1 個數字的乘積、S[i] 為後 n - i - 1 個（即 P[i] 定義後的剩餘數字）之乘積。而我們可以看到實際上對於任意 i 值（0 ≦ i < n - 2）：
P[i + 1] = P[i] * nums[i]
S[i + 1] = S[i] / nums[i]
也就是說我們一開始求完 P[0] 和 S[0] 之後，便可以按照上面的方式往右依序求得 P[1] 、 S[1] 、 P[2] 、 S[2] 、……。
當然，因為我們要存的是質因數次方值，因此我們會需要質因數分解 nums[i]。分解完後更動對應的 P[i] 、 S[i] 各自的質因數次方值來得到 P[i + 1] 和 S[i + 1] 的質因數次方值。
不過如果我們每次修改完來比較每一種可能的質因數來確認是不是互質的話，總體時間複雜度會是 O(n × sqrt(M) × (M ÷ log(M)))，其中 M 為 nums 中的最大值、 sqrt(M) 為 M 的平方根（代表著質因數分解之時間），而 M ÷ log(M) 代表著需要比較的質數數量（漸進逼近）。依舊不甚理想。
而我們可以把這個檢查融入到質因數分解的過程中來降低時間複雜度。我們只需要宣告一個變數 C，代表著有多少質因數滿足兩個乘積的次方值都大於 0。而在質因數分解 nums[i]，每得到一個質因數的次方值就去修改 P[i] 和 S[i] 的對應質因數次方值。而如果：
原本兩者的都大於 0，但在修改後 S[i] 變成 0。則 C 應減去 1（因為少一個質因數滿足條件了）；
原本 P[i] 的值是 0，但在修改後 P[i] 和 S[i] 的次方值都大於 0。則 C 應加上 1。
因為 P[i] 的次方值只會上升、S[i] 的次方值只會下降（不變的次方值當然不影響 C），所以這兩個條件足夠了。
如上我們從 P[i] 與 S[i] 藉由質因數分解得到 P[i] 和 S[i] 的質因數次方值之後，只要檢查 C 是不是 0 即可得到是否互質。如果 C 是 0，代表互質，因此此時的 i + 1 即是所求（只有 i == 0 時比較特別）。
如果全部的 i 值都掃過一遍沒得到互質的乘積的話，則回傳 -1。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
