Prime number test
Check whether an integer is prime: greater than 1 and divisible only by 1 and itself.
Course progress
Problem 5 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
number = 29
Expected output
True
What is happening?
No integer from 2 through the square root of 29 divides it evenly. Therefore, 29 has no positive divisors other than 1 and itself.
Solution strategy
Build the right mental model
After handling values below 2, test possible divisors only up to the square root. Any larger factor would have a smaller paired factor.
Core concepts
math · early return
Complexity
Time O(√n), space O(1).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for prime-number
using System;
class Program
{
static bool IsPrime(int number)
{
if (number < 2) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
for (int divisor = 3; divisor <= number / divisor; divisor += 2)
if (number % divisor == 0) return false;
return true;
}
static void Main()
{
Console.WriteLine(IsPrime(29));
}
}Knowledge check
Questions students often ask
What is the main idea behind prime number test?
After handling values below 2, test possible divisors only up to the square root. Any larger factor would have a smaller paired factor.
What is the time and space complexity of this solution?
Time O(√n), space O(1).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.