Skip to content

Problems — Level 1: Divisibility, Prime, GCD, LCM

এই folder-এ Level 1-এর 15টা problem-এর note থাকবে। Level 0-এর মতোই — প্রতিটা problem-এর জন্য আলাদা .md file, যেখানে নিজের ভাষায় বোঝা, intuition, dry run, code আর ভুলের হিসাব।

কীভাবে problem গুলো use করবে?

প্রতিটা note লেখা হয় ../../../templates/math-problem-note-template.md follow করে — ২০টা section-এর template: problem নিজের ভাষায় → brute force → bottleneck → optimization → dry run → complexity → ভবিষ্যতের নিজেকে এক লাইনের চিঠি। এই level-এ template-এর "brute force আগে" নিয়মটা বিশেষ জরুরি — O(n) factor loop আগে লিখে তারপর O(√n)-এ নামলে শেখাটা গাঁথে।

নিয়ম:

  1. ../README.md-এর recommended order ধরে এগোও
  2. নিজে 20-30 মিনিট চেষ্টা — তারপর concept-notes-এ ফিরে দেখা
  3. Solve হলে Status planned → done

Tracker table

# Problem Difficulty Pattern Inherits from Source Note file Status
011 Divisibility Rules Easy divisibility 001 Classic exercise 011-divisibility-rules.md planned
012 Count Factors Easy √n factor pairs 011 Classic exercise 012-count-factors.md planned
013 Check Prime Easy trial division 012 Classic exercise 013-check-prime.md planned
014 Print All Primes up to N Easy repeated prime check 013 Classic exercise 014-print-all-primes.md planned
015 Sieve of Eratosthenes Medium sieve 014 CP-Algorithms — https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html (related: LeetCode Count Primes — https://leetcode.com/problems/count-primes/) 015-sieve-of-eratosthenes.md planned
016 Prime Factorization Medium peeling primes 013 Classic (related: Project Euler 3 — https://projecteuler.net/problem=3) 016-prime-factorization.md planned
017 Smallest Prime Factor Medium SPF sieve 015 CP-Algorithms sieve variants 017-smallest-prime-factor.md planned
018 GCD using Euclidean Algorithm Easy Euclid — CP-Algorithms — https://cp-algorithms.com/algebra/euclid-algorithm.html 018-gcd-euclidean.md planned
019 Extended GCD Intro Hard back-substitution 018 CP-Algorithms — https://cp-algorithms.com/algebra/extended-euclid-algorithm.html 019-extended-gcd-intro.md planned
020 LCM using GCD Easy lcm = a*b/gcd 018 Classic (related: Project Euler 5 — https://projecteuler.net/problem=5) 020-lcm-using-gcd.md planned
021 Coprime Check Easy gcd = 1 018 Classic exercise 021-coprime-check.md planned
022 Count Coprime Pairs Basic Medium gcd over pairs 021 Classic exercise 022-count-coprime-pairs.md planned
023 Euler Phi Basic Medium totient formula 016, 021 CP-Algorithms — https://cp-algorithms.com/algebra/phi-function.html 023-euler-phi-basic.md planned
024 Number of Divisors Medium exponent formula 016 CSES Counting Divisors — https://cses.fi/problemset/task/1713 024-number-of-divisors.md planned
025 Sum of Divisors Medium exponent formula 024 Classic (harder variant: CSES Sum of Divisors — https://cses.fi/problemset/task/1082) 025-sum-of-divisors.md planned

Problem-দের পারিবারিক গাছ

001 (parity, Level 0)
   └─> 011 (divisibility) ─> 012 (count factors) ─> 013 (prime check)
                                                       ├─> 014 (all primes) ─> 015 (sieve) ─> 017 (SPF)
                                                       └─> 016 (factorization) ─> 023, 024 ─> 025

018 (Euclid GCD) ─┬─> 019 (extended gcd — Hard, Level 2-র সেতু)
                  ├─> 020 (lcm)
                  └─> 021 (coprime) ─> 022 (coprime pairs) ─> 023 (phi)

আটকে গেলে "Inherits from" ধরে এক ধাপ পেছনে যাও — উত্তরের সূত্র প্রায়ই সেখানেই।

একটা ছোট পরামর্শ

এই level-এ অনেক problem-এর দুটো সমাধান থাকবে: একটা সরল (loop-all), একটা চালাক (√n / sieve / formula)। দুটোই লেখো। সরলটা দিয়ে চালাকটার উত্তর verify করা — এই অভ্যাসটা contest আর interview দুই জায়গাতেই বাঁচাবে। আর 019 (Extended GCD) নিয়ে এখন perfection-এর দরকার নেই — Level 2-তে modular inverse করার সময় ওটা আবার সামনে আসবে, তখন আরও অর্থবহ লাগবে।

Concept ঝালাই → ../concept-notes.md। ছবি → ../visualization-ideas.md।