Medium · loop logic

Prime Check

Read an integer and print whether it's prime. Easy to state, and the first problem where how you loop matters as much as whether you loop.

At a glanceTry divisors only up to √N and stop at the first hit — 1 is not prime, 2 is, and the √N bound keeps the loop near a thousand steps for N = 10⁶.

Problem

Input: one integer N (1 ≤ N ≤ 1,000,000).

Output: prime if N is prime, otherwise not prime (exactly these words).

Samples:

Input	Output
`17`	`prime`
`18`	`not prime`

A prime has exactly two divisors: 1 and itself. So 1 is not prime, and 2 is the only even prime.

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — assume, disprove, conclude

Start with bool prime = true;. Loop candidate divisors; the moment one divides evenly (n % i == 0), set prime = false; and break; — one counterexample is enough. Afterwards, print based on the flag.

Hint 2 — you don't need to check up to N

If N has a divisor bigger than √N, it also has one smaller than √N (they pair up: d × (N/d) = N). So looping while i * i <= n is enough — for N = 1,000,000 that's 1,000 candidates instead of a million. Edge cases to handle: N = 1 is not prime; N = 2 is.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool prime = true;
    if (n < 2) prime = false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            prime = false;
            break;
        }
    }
    if (prime) cout << "prime" << endl;
    else cout << "not prime" << endl;
    return 0;
}

The three ideas here — assume-then-disprove, break on first counterexample, and the √N shortcut — recur throughout number problems. A good stretch goal: print all primes up to N (add an outer loop, or research the Sieve of Eratosthenes). Meanwhile, revisit the loop guide for break/continue mechanics, or try Reverse a Number.

Deep dive

Why this works

Assume-then-disprove: start with prime = true and hunt for a single counterexample. That shape underlies every validation loop you will write.

The cost

O(√n) with the i * i <= n bound. For 1,000,000 that is 1,000 iterations instead of 1,000,000 — a thousandfold win for one line.

Where it goes wrong

i <= sqrt(n) recomputes a floating-point square root every iteration and drifts on rounding. i * i <= n is exact and faster.
Forgetting n < 2 makes 0 and 1 prime.

Next step

All primes up to N, done properly: Count the Primes.

Two things to remember

Divisors come in pairs — stop at √n.
1 is not prime; 2 is the only even prime.

🐞 This version fails — open it and try

i * i < n misses perfect squares

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    bool prime = true;
    if (n < 2) prime = false;
    for (int i = 2; i * i < n; i++) {
        if (n % i == 0) {
            prime = false;
            break;
        }
    }
    if (prime) cout << "prime" << endl;
    else cout << "not prime" << endl;
    return 0;
}