素数の因数を計算する

最近面白いアルゴリズムを解けました。Given a number N that could be up to 10^18 and a list of every other prime factor, the requirement is to compute the complete prime factorization. This was basically handled using a brute force search. 最初にNを全因子の積に割った。After this division, consider the interval between each pair of consecutive factors in the given list, including the interval after the last element. Search for a prime number dividing the current quotient in this interval. Add this number to the list, divide the quotient by it, and move on to the next interval. At the last interval, add the quotient, if it exceeds one, else add nothing.
複雑性を考えるのが単純ではない。For an integer of less than or equal to 10^18, there will be less than 40 factors, or 20 intervals of the half-list. Each interval could be on average of size less than 1000, and finding a prime would cost at most 1000 then. This would make the complexity O(20*10^6), which is likely feasible. Note that an increase in interval size reduces the number of possible factors. For example, if N=10^18, and 2, 10^5 are given, only one interval search of O(10^5) is needed(note that this is not a legitimate test case). Thus, although the hypothetical worst case (naïve) estimate of complexity might be 20*10^9 (10^9 is square root of 10^18), the actual complexity is much less.