SyntaxPilot
Courses/Competitive Programming/Lesson 20

Competitive Programming · Lesson 20 of 90 · 12 min

Number theory 2: sieve, smallest prime factor, factorisation

queued

These are the notes for Competitive Programming episode 20 (number theory 2). We build primes from zero, test one number with trial division only up to √x, and meet an original problem, Prime Count, where testing every number up to 5·10^7 one by one gets Time Limit Exceeded. A PT-period roll call turns into the sieve of Eratosthenes, which counts 3001134 primes in well under a second. Then a second original problem, Prime Receipts, asks for the prime factorisation of up to a million numbers; a sticky note on every number (its smallest prime factor) answers each one in O(log x) steps. Three real bugs close the episode: starting at 1, i * i overflowing an int, and a 40 MB array on the stack. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hooks

The PT-period roll call. Students numbered 2 to 30 all stand up. The teacher looks at the first student still standing, number 2, and says: "every multiple of 2, sit down". 4, 6, 8 … sit. The next student still standing is 3: its multiples sit. Then 5, then 7. Whoever is still standing at the end was never a multiple of a smaller number: those are exactly the primes.

Sticky notes. Imagine every number wears a sticky note saying "divide me by this prime first". The same roll call can write the notes: when prime i makes a student sit, it writes i on their note if the note is still empty. To break a number into primes, you just read its note, divide, read the next note, and repeat.

Primes from zero

  • A divisor of x is a number that divides it with no remainder. The divisors of 12 are 1, 2, 3, 4, 6, 12.
  • A prime is a number with exactly two divisors: 1 and itself. 2, 3, 5, 7, 11, 13 … (2 is the only even prime.)
  • A composite number has more than two divisors. 12 = 2 · 2 · 3 is composite.
  • 1 is neither prime nor composite: it has only one divisor. Treating 1 as a prime is a classic bug (you will see it below).
  • The prime factorisation of x writes it as a product of primes: 360 = 2 · 2 · 2 · 3 · 3 · 5 = 2^3 · 3^2 · 5^1. The small number after ^ is the exponent: how many times that prime appears.
  • The fundamental theorem of arithmetic: every whole number x ≥ 2 is a product of primes in exactly one way, apart from the order. So "the" factorisation of 360 is well defined: there is no other set of primes that multiplies to 360.

Testing one number: trial division up to √x

Trial division: try dividing x by d = 2, 3, 4, …; if any x % d == 0, then x is not prime.

You don't need to go all the way to x. Divisors come in pairs: if d divides x, so does x / d.

36 = 1 · 36 = 2 · 18 = 3 · 12 = 4 · 9 = 6 · 6

In every pair the smaller number is at most the square root √x (√36 = 6), because if both were bigger than √x their product would be bigger than x. So if nothing from 2 up to √x divides x, nothing does, and x is prime. In code we write the loop condition as d * d <= x (no floating-point sqrt needed), and compute d * d as a long long so it can never overflow.

For x near 10^7 that is about √10^7 ≈ 3162 tries instead of 10^7. One number: fast. Millions of numbers: not fast enough, as we'll see.

Problem U · Prime Count

Problem U · Prime Count (written for this course). Given n, print how many primes p satisfy 2 ≤ p ≤ n.

1 ≤ n ≤ 5·10^7, time limit 2 seconds.

Sample input Sample output Why
30 10 2 3 5 7 11 13 17 19 23 29
100 25
1 0 no primes at all
2 1 just 2

Brute force: trial division on every number (Time Limit Exceeded)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool isPrime(int x) {
    if (x < 2) return false;
    for (int d = 2; (ll)d * d <= x; d++)
        if (x % d == 0) return false;
    return true;
}

int main() {
    int n;
    cin >> n;
    int cnt = 0;
    for (int x = 2; x <= n; x++)
        if (isPrime(x)) cnt++;
    cout << cnt << "\n";
    return 0;
}
Input Output
30 10
100 25
50000000 Time Limit Exceeded

Why: there are about 3 million primes up to 5·10^7, and proving each one prime takes up to √x ≈ 7000 tries. That is over 10^10 divisions. Composites are cheap (most have a small divisor), the primes are what kill it.

The sieve of Eratosthenes

Flip the question: instead of testing each number, cross out the ones that are not prime. This is the roll call in code, invented in ancient Greece by Eratosthenes. Like a kitchen sieve, it lets the composites fall through and keeps the primes.

  1. Mark every number from 2 to n as "not crossed out".
  2. Go through i = 2, 3, 4, … If i is not crossed out, nothing smaller divided it, so i is prime. Cross out its multiples.
  3. Whatever is never crossed out is prime.

Start crossing at i · i. Every multiple of i below i · i is k · i with k < i, so it has a smaller factor and was already crossed out by an earlier prime. Example: for i = 3, the multiple 6 was crossed out by 2, so 3 can start at 9. It also means that once i · i > n, nothing new gets crossed.

Hand trace to 25

Prime i Crosses out (from i · i) New this time
2 4 6 8 10 12 14 16 18 20 22 24 all of them
3 9 12 15 18 21 24 9 15 21 (12, 18, 24 were already gone)
5 25 25
7 7 · 7 = 49 > 25: nothing stop crossing

Survivors: 2 3 5 7 11 13 17 19 23, nine primes.

The code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    vector<bool> composite(n + 1, false);
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (composite[i]) continue;
        cnt++;                          // i is prime
        for (ll j = (ll)i * i; j <= n; j += i)
            composite[j] = true;
    }
    cout << cnt << "\n";
    return 0;
}

The outer loop still visits every i up to n (to count the primes), but the inner loop only does work for primes, and for primes above √n it does nothing because i * i > n. j is a long long so that i * i cannot overflow (see the mistakes section).

Input Output
30 10
100 25
1 0 (the loop starts at 2, so it never runs)
2 1
50000000 3001134 (about 0.4 s on our test machine)

Why the sieve is so fast: O(n log log n)

Each prime p crosses out about n / p numbers. The total work is

n/2 + n/3 + n/5 + n/7 + n/11 + … ≈ n · log log n

It is a known result that the sum of 1/p over the primes up to n grows like log log n (the logarithm of the logarithm), which grows incredibly slowly: for n = 5·10^7 it is about 3. So the whole sieve is roughly 1.5·10^8 tiny steps, each just setting one flag.

Memory: vector<bool>. A normal bool takes a whole byte, but vector<bool> is special in C++: it packs 8 flags into one byte (one bit per number). 5·10^7 flags take about 6 MB instead of 50 MB.

Problem U2 · Prime Receipts

A shop prints the prime factorisation of each bill amount on the receipt.

Problem U2 · Prime Receipts (written for this course). The first line has q. Each of the next q lines has one amount x. For each x, print its prime factorisation on one line: each prime p in increasing order as p^e, where e is its exponent, separated by spaces.

1 ≤ q ≤ 10^6, 2 ≤ x ≤ 10^7.

Sample input Sample output
4
360
97
1024
9999990
2^3 3^2 5^1
97^1
2^10
2^1 3^3 5^1 7^1 11^1 13^1 37^1

(The programs below print a space after each factor; a trailing space at the end of a line is accepted by almost every judge.)

Brute force: trial division per query (Time Limit Exceeded)

Divide out each d while it divides x, counting how many times. If something bigger than 1 is left at the end, it is one last prime (it can't have two factors both above √ of the original x).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        for (int d = 2; (ll)d * d <= x; d++) {
            int e = 0;
            while (x % d == 0) {
                x /= d;
                e++;
            }
            if (e) cout << d << "^" << e << " ";
        }
        if (x > 1) cout << x << "^1";
        cout << "\n";
    }
    return 0;
}

Real output on the sample:

2^3 3^2 5^1
97^1
2^10
2^1 3^3 5^1 7^1 11^1 13^1 37^1

Correct: 9999990 splits into seven primes. Now the worst case, built inside main: a million queries, each the prime 9999991. Trial division has to try about 3162 divisors to prove each one.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int q = 1000000;                 // worst case, built here
    ll total = 0;
    while (q--) {
        int x = 9999991;             // a prime
        for (int d = 2; (ll)d * d <= x; d++)
            while (x % d == 0) {
                x /= d;
                total++;
            }
        if (x > 1) total++;
    }
    cout << total << " prime factors\n";
    return 0;
}

Result: Time Limit Exceeded. 10^6 queries × √x ≈ 3·10^9 divisions.

The smallest-prime-factor (SPF) sieve

The smallest prime factor of x, spf[x], is the smallest prime that divides it: spf[360] = 2, spf[45] = 3, spf[97] = 97 (a prime's smallest prime factor is itself). This is the sticky note.

Writing the notes: run the sieve, but when prime i reaches a multiple j, write i on j's note only if the note is still empty. Primes are processed from small to large, so the first prime to reach j is its smallest prime factor. (Here the inner loop starts at i, not i · i, so that every prime also gets its own note: spf[i] = i.)

Reading the notes: to factorise x, repeat p = spf[x]; x /= p until x is 1.

360 → (2) 180 → (2) 90 → (2) 45 → (3) 15 → (3) 5 → (5) 1, so 360 = 2^3 · 3^2 · 5^1.

Each step divides x by at least 2, so there are at most log₂ x steps: at most 23 for x ≤ 10^7. Factorising one number is O(log x).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 10000000;
vector<int> spf(N + 1, 0);       // smallest prime factor

void build() {
    for (int i = 2; i <= N; i++)
        if (spf[i] == 0)                // i is prime
            for (int j = i; j <= N; j += i)
                if (spf[j] == 0) spf[j] = i;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    build();
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        while (x > 1) {
            int p = spf[x], e = 0;
            while (x % p == 0) {
                x /= p;
                e++;
            }
            cout << p << "^" << e << " ";
        }
        cout << "\n";
    }
    return 0;
}

Real output on the sample (the same answers):

2^3 3^2 5^1
97^1
2^10
2^1 3^3 5^1 7^1 11^1 13^1 37^1

The spf array lives outside main (a global): 10^7 + 1 ints is 40 MB, and the mistakes section shows what happens if you put it inside main.

And the million primes:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 10000000;
vector<int> spf(N + 1, 0);       // smallest prime factor

void build() {
    for (int i = 2; i <= N; i++)
        if (spf[i] == 0)                // i is prime
            for (int j = i; j <= N; j += i)
                if (spf[j] == 0) spf[j] = i;
}

int main() {
    build();
    int q = 1000000;                 // worst case, built here
    ll total = 0;
    while (q--) {
        int x = 9999991;
        while (x > 1) {
            x /= spf[x];
            total++;
        }
    }
    cout << total << " prime factors\n";
    return 0;
}

Real output: 1000000 prime factors, in about 0.3 s on our test machine, and most of that is building the sieve once. Each query now costs a single step.

Complexity vs the constraints

Approach Time Worst case here Verdict
Trial division on every number ≤ n about n√n / log n (the primes dominate) n = 5·10^7: ≈ 10^10 divisions TLE
Sieve of Eratosthenes O(n log log n) ≈ 1.5·10^8 flag sets 3001134 in ≈ 0.4 s
Trial division per query O(q · √x) 10^6 · 3162 ≈ 3·10^9 TLE
SPF sieve + follow the notes O(N log log N) once + O(log x) per query build once, then ≤ 23 steps per query ≈ 0.3 s
Structure Memory
vector<bool> for n = 5·10^7 ≈ 6 MB (1 bit each)
vector<int> spf for N = 10^7 ≈ 40 MB (4 bytes each)

The rule: one number, test it with trial division to √x. Many numbers up to about 10^7, sieve first, then answer each one cheaply.

Common mistakes (and the real outputs)

Bug 1: starting the sieve at 1

    for (int i = 1; i <= n; i++) {

With n = 30 the output is 1 instead of 10. The loop counts 1 as a prime, then crosses out every multiple of 1 (1 · 1 = 1, 2, 3, … everything), so nothing else survives. 1 is not prime: start at 2.

Bug 2: int j = i * i

        for (int j = i * i; j <= n; j += i)

With n = 50000000 the program crashes: Segmentation fault (exit code 139; a judge shows Runtime Error (SIGSEGV)), with no output. A segmentation fault means the program touched memory it doesn't own. The largest int is 2147483647; 46340² = 2147395600 still fits, but 46341² = 2147488281 does not. For i > 46340, i * i overflows, wraps around to a negative number, j <= n is still true, and composite[j] with a negative index writes outside the vector. Fix: for (ll j = (ll)i * i; j <= n; j += i). Note that (ll)(i * i) is still wrong: the overflow happens before the cast.

Bug 3: a 40 MB array inside main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    const int N = 10000000;
    int spf[N + 1] = {};             // 40 MB, inside main
    for (int i = 2; i <= N; i++)
        if (spf[i] == 0)
            for (int j = i; j <= N; j += i)
                if (spf[j] == 0) spf[j] = i;
    cout << spf[N] << " " << spf[9999991] << "\n";
    return 0;
}

Real result: Segmentation fault before a single line of output.

Stack vs global memory. Ordinary variables declared inside a function live on the stack, a small memory area for function calls, usually a few megabytes (8 MB on our Linux machine, often 1 MB on Windows). A 40 MB array overflows it at once (a stack overflow). Global variables (declared outside every function), static variables and the contents of a vector live elsewhere and can be hundreds of MB. Making the array global (or static int spf[N + 1], or a vector<int>) fixes it; with static the same program prints 2 9999991.

Summary table

Mistake What you see Why Fix
for (int i = 1; i <= n; i++) 1 instead of 10 (n = 30) 1 counted as prime, and it crosses out everything start at i = 2
for (int j = i * i; …) Segmentation fault / Runtime Error (SIGSEGV), n = 5·10^7 i * i overflows int past 46340, negative index for (ll j = (ll)i * i; …)
int spf[10000001]; inside main Segmentation fault / Runtime Error (SIGSEGV), no output 40 MB on a few-MB stack global array, static, or vector
isPrime(x) for every x ≤ 5·10^7 Time Limit Exceeded ≈ 10^10 divisions sieve once

Mini project

Build a reusable prime toolkit file: sieve(n) returning the list of primes, buildSpf(N), factorise(x) returning (prime, exponent) pairs, countDivisors(x) and listDivisors(x). Check every function against a brute force (try every d from 1 to x) for all x ≤ 10^4, then time factorise on a million random numbers up to 10^7.

Practice

These follow the video's homework.

  1. How many numbers ≤ n have exactly 3 divisors? Find a formula, and the answer for n = 100 and n = 10^6.

    Answer If x = p1^e1 · p2^e2 · …, the number of divisors is (e1 + 1)(e2 + 1)…; this equals 3 (a prime) only when x = p^2 for a prime p. So the answer is the number of primes p with p · p ≤ n, i.e. primes ≤ √n. n = 100: 4 (4, 9, 25, 49). n = 10^6: 168 (the primes ≤ 1000). Checked against a brute force for n = 10, 30, 100, 1000 (2, 3, 4, 11).

  2. Compute the number of divisors of x from its factorisation. What is it for 360 and 9999990?

    Answer Each divisor picks an exponent 0…e for every prime independently, so the count is the product of (e + 1). 360 = 2^3 · 3^2 · 5: 4 · 3 · 2 = 24. 9999990 = 2 · 3^3 · 5 · 7 · 11 · 13 · 37: 2 · 4 · 2 · 2 · 2 · 2 · 2 = 256. Both checked by counting every divisor directly. With the SPF sieve this is O(log x) per number.

  3. Print the sum of all primes ≤ 10^7.

    Answer <code>3203324994356</code> (computed with the sieve). It does not fit in an <code>int</code>, so the sum must be a <code>long long</code>. Small check: the primes ≤ 30 sum to 129.

  4. For q queries (x ≤ 10^7), is x a product of exactly two primes (they may be equal)?

    Answer Count prime factors with repetition by following the notes (<code>x /= spf[x]</code>, count the steps); answer YES when the count is 2. Results from running it: 6, 35, 49, 4 and 9999989 → YES; 12 (3 factors), 60 (4), 8 (3), 97 and 9999991 (1, primes) → NO.

  5. Without code: how many primes are there ≤ 50, and which prime is the last one that crosses out anything in a sieve up to 50?

    Answer 15 primes (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47; the sieve program agrees). The last crossing prime is 7 (7 · 7 = 49 ≤ 50); 11 · 11 = 121 > 50.

Quick quiz

Follow the sticky notes: spf[84] = 2, spf[42] = 2, spf[21] = 3, spf[7] = 7. What is 84?

A) 2^2 · 21 · B) 2^2 · 3 · 7 · C) 2 · 3 · 7 · D) 4 · 3 · 7

Answer

B. 84 → 42 → 21 (two 2s) → 7 (a 3) → 1 (a 7): 84 = 2^2 · 3 · 7. A stops at 21, which is not prime; C misses one 2; D uses 4, which is not prime. Running the SPF loop on 84 prints the notes 2 2 3 7.

Interview questions

  1. Why does trial division only need to go up to √x? Divisors come in pairs d · (x / d); the smaller of each pair is at most √x. If none up to √x divides x, none does.
  2. Why does the sieve start crossing at i · i? Any smaller multiple k · i with k < i has a smaller prime factor and was already crossed out.
  3. What is the time complexity of the sieve, and why? O(n log log n): prime p does about n / p work, and the sum of 1/p over primes ≤ n grows like log log n.
  4. How do you factorise many numbers quickly? Build the smallest-prime-factor array with a sieve once, then divide by spf[x] repeatedly: O(log x) per number, since each division at least halves x.
  5. When is a sieve the wrong tool? When you have one or a few very large numbers (say x ≤ 10^12): an array up to 10^12 is impossible, but trial division to √x = 10^6 is fast.
  6. Why can a big local array crash a program? Local variables live on the stack, which is only a few MB; big arrays must be global, static or in a vector.

Glossary

Term Meaning Example
Divisor A number that divides x with no remainder divisors of 12: 1 2 3 4 6 12
Prime A number with exactly two divisors, 1 and itself 2, 3, 5, 97
Composite A number with more than two divisors 12 = 2 · 2 · 3
Divisor pairs d and x / d both divide x 36 = 4 · 9
Square root bound The smaller divisor in a pair is ≤ √x loop while d * d <= x
Trial division Testing divisors d = 2, 3, … up to √x ≈ 3162 tries for x ≈ 10^7
Prime factorisation Writing x as a product of primes 360 = 2^3 · 3^2 · 5
Exponent How many times a prime appears the 3 in 2^3
Fundamental theorem of arithmetic Every x ≥ 2 factorises into primes in exactly one way (up to order) 84 = 2^2 · 3 · 7 only
Sieve of Eratosthenes Find all primes ≤ n by crossing out multiples of each prime 3001134 primes ≤ 5·10^7
Start at i · i Smaller multiples of i are already crossed out 3 starts at 9
O(n log log n) The sieve's running time; log log n is about 3 here ≈ 1.5·10^8 steps for 5·10^7
vector<bool> A C++ vector that stores one bit per element 5·10^7 flags ≈ 6 MB
Smallest prime factor (SPF) The smallest prime dividing x spf[45] = 3, spf[97] = 97
SPF sieve A sieve that writes each number's smallest prime factor if (spf[j] == 0) spf[j] = i;
O(log x) At most about log₂ x steps ≤ 23 steps for x ≤ 10^7
Stack Small memory area for local variables, a few MB int a[10000001] in main crashes
Global variable Declared outside every function; not limited by the stack vector<int> spf(N + 1); above main
Segmentation fault (SIGSEGV) Crash from touching memory the program doesn't own negative index, stack overflow
Integer overflow A value too big for its type wraps around 46341 · 46341 in an int

Summary

  • A prime has exactly two divisors; 1 is not prime. Every x ≥ 2 has exactly one prime factorisation.
  • Trial division tests one number in O(√x), because divisors come in pairs. Doing it for every number up to 5·10^7 gets TLE.
  • The sieve of Eratosthenes crosses out the multiples of each prime, starting at i · i: O(n log log n), 3001134 primes ≤ 5·10^7 in about 0.4 s, 6 MB with vector<bool>.
  • The SPF sieve writes each number's smallest prime factor; then x /= spf[x] factorises any x ≤ 10^7 in at most 23 steps. A million worst-case queries: about 0.3 s instead of TLE.
  • Real bugs: starting at 1 (1 instead of 10), int j = i * i (SIGSEGV past 46340), a 40 MB array inside main (SIGSEGV).

Solutions in C++, Java and Python

Problem U · Prime Count

C++: the sieve program above (30 → 10, 50000000 → 3001134).

Java (tested: 30 → 10, 100 → 25, 1 → 0, 2 → 1, 50000000 → 3001134 in about 2.3 s on our busy test machine). A Java boolean[] uses 1 byte per element, so n = 5·10^7 takes 50 MB; use java.util.BitSet if the memory limit is tight.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        boolean[] composite = new boolean[n + 1];   // 1 byte each: 50 MB for n = 5*10^7
        int cnt = 0;
        for (int i = 2; i <= n; i++) {
            if (composite[i]) continue;
            cnt++;                                  // i is prime
            for (long j = (long) i * i; j <= n; j += i)
                composite[(int) j] = true;
        }
        System.out.println(cnt);
    }
}

Python (tested on the same inputs, same outputs). A plain Python loop over 5·10^7 numbers would be far too slow, so this version crosses out each prime's multiples with one slice assignment, which runs in C, and counts with bytearray.count. On our test machine it printed 3001134 for 5·10^7 in about 1.8 s and used a 50 MB bytearray (plus a temporary of up to 25 MB): that is close to a 2 s limit, so it may or may not pass on a given judge. The outer loop only needs to go to √n here, because counting is done at the end.

import sys

def main():
    n = int(sys.stdin.readline())
    composite = bytearray(n + 1)          # 1 byte per number, all 0
    i = 2
    while i * i <= n:
        if not composite[i]:
            # cross out i*i, i*i + i, ... with one slice assignment (it runs in C)
            composite[i * i::i] = b"\x01" * len(range(i * i, n + 1, i))
        i += 1
    # 2..n is n - 1 numbers; subtract the crossed-out ones
    print(max(0, n - 1 - composite.count(1)))

main()

Problem U2 · Prime Receipts

C++: the SPF program above.

Java (tested on the sample, on 2, 9999991, 10000000 → 2^1, 9999991^1, 2^7 5^7, and on a million random queries, where its output matched the C++ program's byte for byte). The 40 MB int[] is a static field, so it lives on the heap, not the stack. Scanner is too slow for a million numbers, so it reads bytes directly, and it builds all output in one StringBuilder.

import java.io.*;

public class Main {
    static final int N = 10000000;
    static int[] spf = new int[N + 1];              // on the heap, not the stack

    static void build() {
        for (int i = 2; i <= N; i++)
            if (spf[i] == 0)                        // i is prime
                for (int j = i; j <= N; j += i)
                    if (spf[j] == 0) spf[j] = i;
    }

    // fast reader: a million numbers is too many for Scanner
    static DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
    static int nextInt() throws IOException {
        int c = in.read();
        while (c < '0') c = in.read();
        int x = 0;
        while (c >= '0') {
            x = x * 10 + (c - '0');
            c = in.read();
        }
        return x;
    }

    public static void main(String[] args) throws IOException {
        build();
        int q = nextInt();
        StringBuilder out = new StringBuilder();
        while (q-- > 0) {
            int x = nextInt();
            while (x > 1) {
                int p = spf[x], e = 0;
                while (x % p == 0) {
                    x /= p;
                    e++;
                }
                out.append(p).append('^').append(e).append(' ');
            }
            out.append('\n');
        }
        System.out.print(out);
    }
}

Python (tested on the sample and the same edge inputs, and on a million random queries: identical to the C++ output apart from trailing spaces, in about 2 s on our busy test machine; expect it to be near or over the limit on a strict 1 to 2 s judge). The if spf[j] == 0 loop is far too slow in pure Python, so this version uses a different trick to fill the notes with slice assignments: start with spf[x] = x, then go through the primes up to √N from largest to smallest and write p on every multiple from p · p. A smaller prime writes later and overwrites, so each note ends up with the smallest prime factor; numbers no one writes on are primes and keep spf[x] = x. It also sieves only up to the largest query, and uses array("i") (4 bytes per number, 40 MB at N = 10^7) instead of a list of Python ints, which would need several hundred MB.

import sys
from array import array

def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])
    xs = list(map(int, data[1:1 + q]))
    N = max(xs, default=1)                # sieve only as far as needed
    # spf[x] = x at first; that stays true for primes
    spf = array("i", range(N + 1))
    # primes up to sqrt(N), largest first: a smaller prime overwrites later,
    # so every note ends up holding the SMALLEST prime factor
    r = int(N ** 0.5)
    small = bytearray(r + 1)
    primes = []
    for i in range(2, r + 1):
        if not small[i]:
            primes.append(i)
            small[i * i::i] = b"\x01" * len(range(i * i, r + 1, i))
    for p in reversed(primes):
        cnt = len(range(p * p, N + 1, p))
        spf[p * p::p] = array("i", [p]) * cnt
    out = []
    for x in xs:
        parts = []
        while x > 1:
            p = spf[x]
            e = 0
            while x % p == 0:
                x //= p
                e += 1
            parts.append(f"{p}^{e}")
        out.append(" ".join(parts))
    sys.stdout.write("\n".join(out) + "\n")

main()

Next episode: Modular arithmetic and fast exponentiation.