Flag: scriptCTF{7H3_m0r3_f4C70r5_7h3_b3773r_9d4c573d49cc}

TL;DR

Find the longest subsequence of the given integers whose GCD > 1. This is equivalent to: pick as many numbers as possible that share at least one prime factor. Count, for each prime pp, how many input numbers are divisible by pp; the maximum of these counts is the answer.

We connected to the service, parsed the numbers, computed the max prime-hit count via fast factorization, sent the answer, and received the flag above.

Challenge

• Name: More Divisors

• Category: Programming

• Remote: nc play.scriptsorcerers.xyz 10373

• Prompt (paraphrased): “Find length of the longest subsequence with gcd > 1.”

Sample server output

16602 97751 95140 92323 16041 113382 ... 

Key Insight (Math)

Let the chosen subsequence be SS. If gcd(S) > 1, then there exists a prime pp dividing every element of SS. Conversely, any set of numbers all divisible by the same prime pp has GCD at least pp (>1).

Therefore, the problem reduces to:

For each prime pp, count how many input numbers are divisible by pp. The answer is the maximum of these counts.

This avoids any dynamic programming on subsequences—just prime-factor counting.

Approach

1. Receive a line (or lines) of integers from the TCP service.

2. Parse all integers. Ignore ≤1\le 1 if present.

3. Prime sieve up to ⌊max⁡(A)⌋\lfloor\sqrt{\max(A)}\rfloor to get small primes.

4. Factorize each number by trial division with the primes; collect only distinct prime factors per number (avoid double-counting).

5. Tally occurrences in a prime -> count map.

6. Return the maximum count; send it back to the service.

7. Read final message — the flag.

Time complexity:

• Sieve: O(Mlog⁡log⁡M)O(M \log \log M) where M=⌊max⁡(A)⌋M = \lfloor\sqrt{\max(A)}\rfloor.

• Factoring: roughly O(N⋅ω(Ai))O(N \cdot \omega(A_i)) where ω(x)\omega(x) = number of distinct prime factors (usually tiny).

• Overall: fast for NN up to tens of thousands and numbers up to ~10910^9–101210^{12} when mostly smooth.

Implementation (Python)

We used pwntools for a clean TCP interaction, but you could use socket just as well.

# solve_more_divisors.py
# pip install pwntools
import re
import math
from collections import defaultdict
from pwn import remote

def primes_upto(n: int):
    if n < 2:
        return []
    sieve = bytearray(b"\x01") * (n + 1)
    sieve[0:2] = b"\x00\x00"
    r = int(n**0.5)
    for p in range(2, r + 1):
        if sieve[p]:
            step = p
            start = p * p
            sieve[start:n + 1:step] = b"\x00" * (((n - start) // step) + 1)
    return [i for i, isprime in enumerate(sieve) if isprime]

def factorize_distinct(n: int, primes):
    fs = set()
    for p in primes:
        if p * p > n:
            break
        if n % p == 0:
            fs.add(p)
            while n % p == 0:
                n //= p
    if n > 1:
        fs.add(n)
    return fs

def longest_subseq_len(nums):
    if not nums:
        return 0
    mx = max(nums)
    primes = primes_upto(int(math.isqrt(mx)) + 1)
    counts = defaultdict(int)
    for x in nums:
        if x <= 1:
            continue
        for p in factorize_distinct(x, primes):
            counts[p] += 1
    return max(counts.values()) if counts else 0

def parse_ints(s: str):
    return list(map(int, re.findall(r"\d+", s)))

def main():
    HOST, PORT = "play.scriptsorcerers.xyz", 10373
    r = remote(HOST, PORT)

    # Read aggressively until the server pauses or prompts
    buf = b""
    while True:
        try:
            chunk = r.recv(timeout=1.0)
            if not chunk:
                break
            buf += chunk
            if any(key in buf for key in [b"answer", b"Answer", b"ANS", b"?", b":"]):
                break
        except EOFError:
            break
        except Exception:
            break

    text = buf.decode(errors="ignore")
    nums = parse_ints(text)
    ans = longest_subseq_len(nums)

    r.sendline(str(ans).encode())

    # Print any final server message/flag
    try:
        tail = r.recvall(timeout=3).decode(errors="ignore")
        if tail:
            print(tail)
    except Exception:
        pass

if __name__ == "__main__":
    main()

Step‑by‑Step (What we did)

1. Connect: nc play.scriptsorcerers.xyz 10373 to see the format.

2. Recognize the trick: GCD>1 subsequence ⇒ numbers share a prime.

3. Write solver to count prime hits across inputs (distinct factors only).

4. Run: python3 solve_more_divisors.py.

5. Observe the script send the length and print the server response.

6. Retrieve flag: scriptCTF{7H3_m0r3_f4C70r5_7h3_b3773r_9d4c573d49cc}.

Validation & Pitfalls

• Distinct factors per number: don’t count the same prime twice for one value (e.g., 12 shouldn’t add 2 twice).

• Ones / zeros: ignore 1; if 0 appears (unlikely), treat it carefully (divisible by any p) — but service did not include 0.

• Multiple rounds: some services send several batches; wrap receive/compute/send in a loop if needed.

• Huge values: for >1012>10^{12}, consider Pollard–Rho. Not needed here.

Alternative Approach (bounded values)

If all numbers ≤2×105\leq 2\times10^5, build a frequency array cnt[x] and for each p sum cnt[k*p] over multiples—this avoids per-number factoring. Our factorization approach is more general.

Takeaways

• “GCD>1 subsequence” is a prime-sharing frequency problem.

• Counting occurrences per prime solves it in near-linear time.

• For networking tasks, keep parsing resilient and avoid assumptions about prompts.