A senior programmer like me knows that primality-based problems like the one posed in your link are easily gamed.
Testing for small prime factors is easy - brute force is your friend. Testing for large prime factors requires more effort. So the first trick is to figure out the bounds to the problem. Is it int32? Then brute-force it. Is it int64, where you might have a value like the Mersenne prime 2^61-1? Perhaps it's time to pull out a math reference. Is it longer, like an unbounded Python int? Definitely switch to something like the GNU Multiple Precision Arithmetic Library.
In this case, the maximum value is 1,000, which means we can enumerate all distinct prime values in that range, and test for its presence in each input value, one one-by-one:
# list from https://www.math.uchicago.edu/~luis/allprimes.html
_primes = [
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271,
277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353,
359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433,
439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677,
683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769,
773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859,
863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953,
967, 971, 977, 983, 991, 997]
def distinctPrimeFactors(nums: list[int]) -> int:
if __debug__:
# The problem definition gives these constraints
assert 1 <= len(nums) <= 10_000, "size out of range"
assert all(2 <= num <= 1000 for num in nums), "num out of range"
num_distinct = 0
for p in _primes:
for num in nums:
if num % p == 0:
num_distinct += 1
break
return num_distinct
That worked without testing, though I felt better after I ran the test suite, which found no errors. Here's the test suite:
import unittest
class TestExamples(unittest.TestCase):
def test_example_1(self):
self.assertEqual(distinctPrimeFactors([2,4,3,7,10,6]), 4)
def test_example_2(self):
self.assertEqual(distinctPrimeFactors([2,4,8,16]), 1)
def test_2_is_valid(self):
self.assertEqual(distinctPrimeFactors([2]), 1)
def test_1000_is_valid(self):
self.assertEqual(distinctPrimeFactors([1_000]), 2) # (2*5)**3
def test_10_000_values_is_valid(self):
values = _primes[:20] * (10_000 // 20)
assert len(values) == 10_000
self.assertEqual(distinctPrimeFactors(values), 20)
@unittest.skipUnless(__debug__, "can only test in debug mode")
class TestConstraints(unittest.TestCase):
def test_too_few(self):
with self.assertRaisesRegex(AssertionError, "size out of range"):
distinctPrimeFactors([])
def test_too_many(self):
with self.assertRaisesRegex(AssertionError, "size out of range"):
distinctPrimeFactors([2]*10_001)
def test_num_too_small(self):
with self.assertRaisesRegex(AssertionError, "num out of range"):
distinctPrimeFactors([1])
def test_num_too_large(self):
with self.assertRaisesRegex(AssertionError, "num out of range"):
distinctPrimeFactors([1_001])
if __name__ == "__main__":
unittest.main()
I had two typos in my test suite (an "=" for "==", and a ", 20))" instead of "), 20)"), and my original test_num_too_large() tested 10_001 instead of the boundary case of 1_001, so three mistakes in total.
If I had no internet access, I would compute that table thusly:
_primes = [2]
for value in range(3, 1000):
if all(value % p > 0 for p in _primes):
_primes.append(value)
Do let me know of any remaining mistakes.
What kind of senior programmers do you work with who can't handle something like this?
EDIT: For fun I wrote an implementation based on sympy's integer factorization:
from sympy.ntheory import factorint
def distinctPrimeFactors(nums: list[int]) -> int:
distinct_factors = set()
for num in nums:
distinct_factors.update(factorint(num))
return len(distinct_factors)
Here's a new test case, which takes about 17 seconds to run:
def test_Mersenne(self):
self.assertEqual(distinctPrimeFactors(
[2**44497-1, 2,4,3,7,10,6]), 5)