Halving and square-root work
Recognize logarithmic progress and build a prime test with a safe inclusive boundary.
Remove a fraction, not a fixed amount
Repeated integer halving of 20 follows 20 → 10 → 5 → 2 → 1: four divisions. For positive n, the count until the value is at most one is floor(log₂ n). Repeated subtraction of two instead needs about n/2 steps and is linear.
Doubling from one visits powers of two: 1, 2, 4, 8, 16 for n = 20. This makes floor(log₂ n) + 1 visits. Starting at zero never progresses, and an unbounded multiplication can overflow. A wide counter plus a stated upper bound makes the demonstration safe.
// Complete C++23 program. Input: 1 <= n <= 10^18.
#include <iostream>
int halvingSteps(long long value) {
int steps = 0;
while (value > 1) {
value /= 2;
++steps;
}
return steps;
}
int main() {
long long n = 0;
std::cin >> n;
std::cout << halvingSteps(n) << '\n';
}A fresh halving loop repeated n times
If an outer loop performs n iterations and starts a fresh halving process at n each time, it makes n floor(log₂ n) inner visits. The conventional bound is O(n log n), with O(n(1 + log n)) covering the small boundary cleanly.
Do not infer n log n just because one loop doubles. If the inner costs vary with that doubling value, add their actual lengths as in the growing-chunks lesson.
A composite number has a small factor
If x = ab and both positive factors exceeded √x, their product would exceed x. Therefore a composite x has a factor at or below √x. Reject values below two, then test candidate divisors through that boundary.
Use divisor <= value / divisor with positive divisor to avoid forming a possibly overflowing divisor * divisor. Equality matters: 49 must test 7. Return true only after all candidates fail; returning true inside the loop after checking 2 would incorrectly accept 9.
Growth explorer
Idealized operation counts show growth. Actual runtime also depends on the implementation and machine.
O(1)1O(log n)7O(n)100O(n log n)665O(n²)10,000Bar lengths use a logarithmic scale. Logarithms use base 2.
Guided simulation · Change the inputs to test your understanding.
Why must the prime-test condition include equality at the square-root boundary?
Turn the idea into code
Write isPrime(int value) for −10⁹ ≤ value ≤ 10⁹. Return a bool and let main print YES or NO. Include tests −7, 0, 1, 2, 9, 49, and 97.
Give me a hint
Reject values below two. Return false on a divisor; place the final true after the loop.
Show the explained solution
Every composite positive value has a tested divisor at or below its square root. A divisor is sufficient evidence to reject; no divisor in the required range proves primality for values at least two.
// Complete C++23 program. Input: -10^9 <= value <= 10^9.
#include <iostream>
bool isPrime(int value) {
if (value < 2) return false;
for (int divisor = 2; divisor <= value / divisor; ++divisor) {
if (value % divisor == 0) return false;
}
return true;
}
int main() {
int value = 0;
std::cin >> value;
std::cout << (isPrime(value) ? "YES\n" : "NO\n");
}Your notes
Mark complete when you can explain it yourself.