17Prime
- Check
- No divisors in 2..4
Check Prime Number in C#
What you’ll learn
- What makes a number prime (exactly two positive divisors).
- Why checking divisors only up to sqrt(n) is enough.
- Two C# programs: one-number test and prime listing in a range.
- A live preview, edge cases, and optimization notes.
Overview
A prime number is greater than 1 and divisible only by 1 and itself. Instead of checking all numbers up to n - 1, we stop at sqrt(n) to keep checks efficient.
Single check
Determine if one value like 17 is prime.
Range listing
Print all primes from 1 to 20 using the same helper.
Fast bound
Stop divisor checks at i * i <= n.
Prerequisites
Loops, modulo operator %, and integer comparisons.
- Prime numbers are integers greater than 1.
- If any divisor exists in
[2, sqrt(n)],nis not prime.
Understanding the concept of prime numbers
A prime number has exactly two positive divisors: 1 and itself. Examples: 2, 3, 5, 7, 11, 13.
Values <= 1 are not prime, and 2 is the only even prime. A natural number greater than 1 that is not prime is called composite.
Square-root bound
If n = a × b, then at least one of a or b is <= sqrt(n). So checking divisibility only up to sqrt(n) is sufficient.
Result
No divisor up to sqrt(n) means n is prime.
Quick examples
18Not prime
- Check
- Divisible by 2
2Prime
- Special
- Only even prime
Live preview
Runs the same square-root trial-division logic as the C# examples.
Algorithm
Goal: determine whether integer n is prime.
Reject small values
If n <= 1, return false.
Check divisors
Loop i from 2 while i * i <= n.
Return verdict
If any n % i == 0, not prime; otherwise prime.
📜 Pseudocode
Pseudocode
function isPrime(n):
if n <= 1:
return false
for i from 2 while i * i <= n:
if n mod i == 0:
return false
return true1
Check one number
Reference program: tests whether 17 is prime using trial division up to sqrt(n).
c#
using System;
class Program
{
static bool IsPrime(int number)
{
if (number <= 1)
return false;
for (int i = 2; (long)i * i <= number; i++)
{
if (number % i == 0)
return false;
}
return true;
}
static void Main()
{
int testNumber = 17;
if (IsPrime(testNumber))
Console.WriteLine($"{testNumber} is a prime number.");
else
Console.WriteLine($"{testNumber} is not a prime number.");
}
}2Prime numbers in range
Prime numbers in range 1 to 20
Reuses IsPrime inside a range loop — matches the reference range output.
c#
using System;
class Program
{
static bool IsPrime(int number)
{
if (number <= 1)
return false;
for (int i = 2; (long)i * i <= number; i++)
{
if (number % i == 0)
return false;
}
return true;
}
static void Main()
{
Console.WriteLine("Prime Numbers in the Range 1 to 20:");
for (int i = 1; i <= 20; i++)
{
if (IsPrime(i))
Console.Write($"{i} ");
}
Console.WriteLine();
}
}Optimization and alternatives
Square-root bound. Use i * i <= n (or cast to long) instead of looping to n - 1.
Skip evens. After handling 2, test only odd divisors to reduce constant work.
Math.Sqrt. You can write i <= Math.Sqrt(number), but integer multiplication avoids floating-point rounding issues.
❓ FAQ
A prime number is an integer greater than 1 that has exactly two positive divisors: 1 and itself.
No. By definition, prime numbers start from 2.
If n has a factor bigger than sqrt(n), the paired factor must be smaller than sqrt(n), so checking up to sqrt(n) is enough.
2 has only two divisors: 1 and 2. It is also the only even prime.
In this tutorial, primality is defined for integers greater than 1, so negatives are not prime.
The square-root trial division check runs in O(sqrt(n)) time and O(1) extra space.
🔄 Input / output examples
n | Result |
|---|---|
17 | Prime |
18 | Not prime (divisible by 2) |
1 | Not prime |
2 | Prime |
Edge cases and pitfalls
n <= 1Not prime
Values 1, 0, and negatives are not prime in this tutorial.
n = 2Smallest prime
2 is prime and the only even prime.
OverflowLarge
Large n
Use (long)i * i <= number to avoid overflow in the loop condition.
⏱️ Time and space complexity
| Method | Time | Extra space |
|---|---|---|
| Single prime check (sqrt bound) | O(√n) | O(1) |
| Check all numbers in range 1..U | about O(U√U) | O(1) |
Summary
- Primes are integers > 1 with exactly two divisors.
- Use trial division up to
sqrt(n)—O(sqrt(n))per check. - From
1to20, primes are2 3 5 7 11 13 17 19.
Did you know?
2 is the only even prime number. 1 is neither prime nor composite.
About the author
9 people found this page helpful