56Composite
- Factors
- 2, 2, 2, 7
Find Prime Factors in C#
What you’ll learn
- What prime factors are and how repeated factors are represented.
- A clear trial division approach and a faster sqrt-based variant.
- How factorization output stays naturally sorted in non-decreasing order.
- A live preview, input guards, and common interview edge cases.
Overview
For 56, the prime factorization is 2 × 2 × 2 × 7. The algorithm tries divisors in increasing order, repeatedly divides out matching factors, and shrinks the number until all prime pieces are printed.
Two C# examples
A simple all-divisors loop and an optimized sqrt-style version.
Live preview
Try 56, 17, or 360 instantly.
Input guard
We enforce n >= 2 for valid prime factorization.
Prerequisites
for/while loops, remainder %, and integer division.
- Prime number basics and divisibility checks with
n % d == 0. - Reading C# console output and tracing loop states.
What are prime factors?
Prime factors are prime numbers whose product gives the original number. Repetition matters: 12 = 2 × 2 × 3.
Trial division prints factors in sorted order automatically when divisors are tested from small to large.
Why this factor order works
If a small prime factor exists, it appears before larger factors. By dividing it out completely, remaining factors can be found similarly until the number becomes 1 or one leftover prime remains.
Check
Multiplying printed factors reconstructs the original input n.
Quick examples
17Prime
- Factors
- 17 only
360Many
- Starts with
- 2, 2, 2, 3, 3, 5…
Live preview
Uses the optimized approach: remove 2s first, then test odd divisors.
Algorithm (trial division)
Goal: print prime factors of n in non-decreasing order.
Validate input
Reject when n < 2.
Strip factors
Repeatedly divide by each divisor while it divides exactly.
Finish with leftover prime
If remainder is greater than 1, print it as the final prime factor.
📜 Pseudocode
Pseudocode
function printPrimeFactors(n):
if n < 2:
stop
while n mod 2 == 0:
print 2
n = n / 2
i = 3
while i * i <= n:
while n mod i == 0:
print i
n = n / i
i = i + 2
if n > 1:
print n1
Simple trial division
Reference program: prints prime factors of 56 using a straightforward loop from 2 upward.
c#
using System;
class Program
{
static void PrintPrimeFactors(int n)
{
if (n < 2)
{
Console.WriteLine("Enter n >= 2.");
return;
}
Console.Write($"Prime factors of {n} are: ");
for (int i = 2; i <= n; i++)
{
while (n % i == 0)
{
Console.Write($"{i} ");
n /= i;
}
}
Console.WriteLine();
}
static void Main()
{
PrintPrimeFactors(56);
}
}2
Optimized sqrt-style version
Strip all 2s first, then test odd divisors only up to sqrt(n) — faster for larger inputs.
c#
using System;
class Program
{
static void PrintPrimeFactors(int n)
{
if (n < 2)
{
Console.WriteLine("Enter n >= 2.");
return;
}
Console.Write($"Prime factors of {n} are: ");
while (n % 2 == 0)
{
Console.Write("2 ");
n /= 2;
}
for (int i = 3; (long)i * i <= n; i += 2)
{
while (n % i == 0)
{
Console.Write($"{i} ");
n /= i;
}
}
if (n > 1)
Console.Write($"{n} ");
Console.WriteLine();
}
static void Main()
{
PrintPrimeFactors(56);
}
}Optimization notes
After removing factor 2, test only odd divisors up to sqrt(n).
Use (long)i * i <= n in C# to avoid overflow when n is large.
❓ FAQ
A prime factor is a prime number that divides n exactly. Example: 56 = 2 x 2 x 2 x 7.
The same prime can repeat many times, so we keep dividing while it still divides.
Prime factorization is usually defined for n >= 2, so this tutorial rejects smaller values.
Yes. Trial division from small to large naturally prints factors in non-decreasing order.
You only test divisors up to sqrt(current remainder), then handle any leftover prime greater than 1.
The simple loop is up to O(n). The optimized sqrt approach is about O(sqrt n) time with O(1) extra space.
🔄 Input / output examples
| Input | Prime factors |
|---|---|
56 | 2 2 2 7 |
12 | 2 2 3 |
17 | 17 |
360 | 2 2 2 3 3 5 |
Edge cases and pitfalls
n < 2
Invalid input
Prime factorization is defined for integers 2 and above.
Prime n
n = 17
A prime returns itself as the only factor.
OverflowLarge
Large n
Cast to long when comparing i * i to n.
⏱️ Time and space complexity
| Version | Time | Extra space |
|---|---|---|
| Simple trial division | up to O(n) | O(1) |
| Optimized sqrt-style | about O(√n) | O(1) |
Summary
- Trial division prints prime factors in sorted order.
- For
56, output is2 2 2 7. - The sqrt-bounded approach improves runtime for larger inputs.
Did you know?
Every integer greater than 1 has a unique prime factorization (ignoring order). That is why trial division from small to large always reconstructs the same factors.
About the author
8 people found this page helpful