Prime Numbers
Determine if a number is prime using Trial Division.
Ready to check primality.
29
Intuition
To check if a number N is prime, we try to divide it by every number from 2 up to N-1. If none divide it evenly, it's prime.
Concept
- Prime Number: A number greater than 1 that has exactly two factors: 1 and itself.
- Composite Number: A number that has more than two factors.
- Optimization: We only need to check divisors up to √N. If N has a factor larger than √N, it must also have a corresponding factor smaller than √N.
How it Works
Algorithm:
- If N ≤ 1, return False.
- Loop
ifrom 2 to√N. - If
N % i == 0, return False (found a factor). - If loop finishes without finding a factor, return True.
Step-by-Step Breakdown
Watch the visualization:
- Green boxes show numbers we checked that didn't divide N.
- Red box shows a number that divides N (proving it's composite).
- Notice we stop early if we find a factor!
When to Use
- Checking primality for small to medium numbers (up to 10^12 is feasible).
- Cryptography key generation (though probabilistic tests like Miller-Rabin are used for huge numbers).
When NOT to Use
- For extremely large numbers (hundreds of digits).
- When you need to generate many primes (use Sieve of Eratosthenes instead).
How to Identify
"Is N prime?", "Find factors", "Number theory problems".
Frequently Asked Questions
What is Prime Numbers?
Determine if a number is prime using Trial Division.
What is the time complexity of Prime Numbers?
The time complexity is: Best case varies, Average case O(√N), Worst case varies. Space complexity is varies.