Divisibility & Primes
Learn divisibility rules, factors, multiples, prime numbers, and the Sieve of Eratosthenes.
Lessons
1. Intro
(The Goal)
2. What is Divisibility
(When division leaves no remainder)
3. Factors and Multiples
(Two sides of divisibility)
4. Divisibility Rule - 2
(Last digit even)
5. Divisibility Rule - 5
(Last digit 0 or 5)
6. Divisibility Rule - 10
(Last digit 0)
7. Divisibility Rule - 3
(Sum of digits divisible by 3)
8. Divisibility Rule - 9
(Sum of digits divisible by 9)
9. Divisibility Rule - 4
(Last two digits divisible by 4)
10. Prime Numbers
(Only two factors)
11. Composite Numbers
(More than two factors)
12. Prime Factorization
(Breaking down into primes)
13. Fundamental Theorem of Arithmetic
(Unique prime factorization)
14. Finding All Divisors
(Check up to square root)
15. Finding Divisors - Implementation
(Loop to square root)
16. Testing for Primality
(Check divisors up to square root)
17. Quiz: Divisibility Rules
(Knowledge check)
18. The Sieve of Eratosthenes
(Ancient algorithm for primes)
19. Sieve Example
(Finding primes up to 30)
20. Sieve - Implementation
(Boolean array approach)
21. Sieve Optimization
(Start at p squared)
22. Problem - Count Primes
(Entry problem)
23. Count Primes - Insight
(Use the sieve)
24. Count Primes - Algorithm
(Sieve then count)
25. Count Primes - Pseudocode
(Implementation ready)
26. Problem - Ugly Number
(Prime factors check)
27. Ugly Number - Insight
(Divide out allowed primes)
28. Ugly Number - Algorithm
(Divide and check remainder)
29. Ugly Number - Pseudocode
(Implementation ready)
30. Problem - Perfect Number
(Sum of proper divisors)
31. Perfect Number - Insight
(Find divisors efficiently)
32. Perfect Number - Algorithm
(Sum proper divisors)
33. Perfect Number - Pseudocode
(Implementation ready)
34. Quiz: Prime Numbers
(Knowledge check)
35. Greatest Common Divisor
(Largest shared factor)
36. Least Common Multiple
(Smallest shared multiple)
37. Applications of Divisibility
(Where these concepts appear)
38. How Many Primes Exist
(Infinitely many)
39. Coprime Numbers
(GCD equals 1)
40. Problem - Largest Prime Factor
Find the biggest prime
41. Largest Prime Factor - Insight
The key observation
42. Largest Prime Factor - Algorithm
Step by step approach
43. Largest Prime Factor - Implementation
The pseudocode
44. Section Recap
What we learned