primed4action¶

Link

Hack The Box

Description¶

Intelligence units have intercepted a list of numbers. They seem to be used in a peculiar way - the adversary seems to be sending a list of numbers, most of which are garbage, but two of which are prime. These 2 prime numbers appear to form a key, which is obtained by multiplying the two.

Your answer is the product of the two prime numbers. Find the key and help us solve the case.

Example Input 2 6 7 18 6

Output 14

Notes¶

Because “odd” is only a costume, not a badge of authenticity.

All prime numbers except 2 are odd, but not all odd numbers are prime. Being odd just means “not divisible by 2.”

Tip

Prime means “not divisible by anything except 1 and itself.” That’s a much stricter club.

Your original filter was:

x % 2 != 0 or x == 2

That asks only one question: “Are you odd, or are you 2?” Plenty of criminals pass that test.

Look at these:

9 → odd, but 9 = 3 × 3
15 → odd, but 15 = 3 × 5
21 → odd, but 21 = 3 × 7
493 → odd, but 493 = 17 × 29
3261 → odd, but 3261 = 3 × 1087

They walk straight through the door because they’re odd, even though they’re obviously composite.

So in your intercepted list, many numbers looked prime because:

They weren’t even
They weren’t small
They felt “random”

But mathematics doesn’t care about vibes. It cares about divisibility.

A real prime must survive this interrogation:

“Can I be divided cleanly by any number greater than 1 and less than or equal to my square root?”

If yes → impostor. If no → genuine prime.

Odd numbers are suspects. Prime numbers are the ones that survive questioning.

Your first version was checking dress code. The fixed version checks identity.

Why the square root bound works¶

The key line in the prime check is:

for i in range(2, int(n**0.5) + 1):

To test if a number is prime, you could try dividing by every smaller number, but that is slow. There is a shortcut:

If a number n is not prime, then n = a × b. At least one of a or b must be less than or equal to √n. So if no number from 2 up to √n divides n, then n must be prime.

That is why the loop stops at:

n**0.5 → square root of n
int(...) → convert to integer
+ 1 → include the last possible divisor

This keeps the algorithm fast without missing any composite numbers.

Gotcha

primed4action.py