Можно заключить, что умножение не создаст каких-либо новых простых чисел, поэтому мы можем просто проверить каждое число по отдельности.

Нам нужно знать только простые числа с точностью до sqrt(1000).

Если после деления n на все эти простые числа n все еще больше 1, то остается большое простое число.

Это связано с тем, что достаточно попробовать делители вплоть до sqrt(n), чтобы проверить, является ли число простым.

792 (2 * 2 * 2 * 3 * 3 * 11). Различными простыми числами являются 2, 3 и 11, а n уменьшается до 1.
723 (3 * 241). После проверки простых чисел [2 ... 31], n уменьшается до 241, и, следовательно, 241 является большим простым числом.

def distinctPrimeFactors(nums): result = [] for i in range (len(nums)) : square_root = int(math.sqrt(nums[i])) for prime_num in range(2, square_root + 1) : if (nums[i] % prime_num == 0) : result.append(prime_num) while (nums[i] % prime_num == 0) : nums[i] = nums[i] // prime_num if (nums[i] >= 2) : result.append(nums[i]) result = set(result) return len(result)

[Тестовое Google] Простые множители произведения массива

Оформите Premium