014 — Print All Primes up to N

013-এ তুমি একটা সংখ্যা prime কিনা বলতে শিখেছ। আজ স্বাভাবিক পরের প্রশ্ন — N পর্যন্ত সব prime বের করো। প্রথম ভাবনাটা সরল: প্রতিটা সংখ্যাকে আলাদা করে 013-এর is_prime দিয়ে যাচাই করো। কাজ করবে, কিন্তু একটু ধীর — আর সেই ধীরগতিই আমাদের পরের problem (015, Sieve)-এর দিকে ঠেলে দেবে। তাই এই note-টা শুধু সমাধান নয়, একটা সেতু: কেন "এক-এক করে check" থেকে "একসাথে কেটে ফেলা"-য় যেতে হয়, সেটা এখানে গাঁথা হবে।

Source

• Original source: Classic beginner exercise
• Platform: Classic exercise
• Topic: Math-based programming fundamentals → Level 1: Divisibility, Prime, GCD, LCM
• Difficulty: Easy
• Pattern: repeated prime check
• Basic idea inherited from: 013 (Check Prime)

1. Problem in simple words

একটা সংখ্যা N দেওয়া আছে। 2 থেকে N পর্যন্ত যত prime আছে, সবগুলো একটা তালিকায় বের করতে হবে।

যেমন N = 20 হলে উত্তর: [2, 3, 5, 7, 11, 13, 17, 19]।

013-এ আমরা একটা সংখ্যা prime কিনা দেখতাম; এখানে সেই কাজটাই 2 থেকে N পর্যন্ত প্রতিটা সংখ্যায় চালিয়ে যারা prime, তাদের জড়ো করব।

2. What is the math idea?

কোনো নতুন গণিত নয় — মূল idea হলো repeated prime check: 013-এর is_prime কে একটা loop-এ বসিয়ে 2 থেকে N পর্যন্ত প্রতিটা সংখ্যায় ডাকো, যেটা prime সেটাকে তালিকায় রাখো।

result = []
2 থেকে N পর্যন্ত প্রতিটা num:
    যদি is_prime(num):
        result-এ num যোগ করো
return result

এটুকুই। আসল শেখা এখানে algorithm-এ নয়, বরং খরচ নিয়ে ভাবায় — প্রতিটা সংখ্যার জন্য আলাদা √n check চালালে মোট কত কাজ হয়, আর সেটা কমানো যায় কিনা (Section 8 ও 18)।

3. Which basic idea does this inherit from?

সরাসরি 013 (Check Prime) থেকে — আক্ষরিক অর্থেই এটা 013-কে একটা loop-এ মুড়ে দেওয়া।

013:  is_prime(n)              -> একটা সংখ্যা prime?
014:  for num in 2..N:         -> প্রতিটা সংখ্যায় 013 ডাকো,
          if is_prime(num): ...    prime হলে জড়ো করো

মানে 013 ছিল একক প্রশ্ন, 014 হলো সেই প্রশ্ন বারবার করে উত্তর জড়ো করা। এটা একই inheritance-সুর: একটা ছোট নির্ভরযোগ্য কাজ (prime check) পেয়ে গেলে, তাকে loop-এ বসিয়েই বড় কাজ (সব prime তালিকা) হয়ে যায়। 013-এর check ভুল থাকলে এখানে পুরো তালিকাই ভুল হবে — তাই ভিত্তিটা পোক্ত হওয়া জরুরি।

4. Real-life analogy

ভাবো একটা বড় ঝুড়ি ভর্তি ফল, আর তোমাকে শুধু পাকা ফলগুলো আলাদা করতে হবে।

• ঝুড়ির ফল = 2 থেকে N পর্যন্ত সব সংখ্যা
• "এই ফলটা পাকা?" পরীক্ষা = is_prime(num) (013-এর কাজ)
• পাকা হলে আলাদা ঝুড়িতে রাখা = result.append(num)

তুমি এক-একটা ফল হাতে নিয়ে পরীক্ষা করছ, পাকা হলে সরিয়ে রাখছ — শেষে আলাদা ঝুড়িতে শুধু পাকা ফল (prime)। এই "এক-এক করে পরীক্ষা" পদ্ধতি কাজ করে, কিন্তু ফল অনেক হলে সময় লাগে — তখন মনে প্রশ্ন জাগে, "এক-একটা না দেখে কি একসাথে বাছা যায়?" সেই প্রশ্নের উত্তরই 015 (Sieve)।

5. Visual explanation

N = 20-এ এক-এক করে check চলছে, পাকা (prime) গুলো ডান ঝুড়িতে জমছে:

num :  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20
is_prime?
       P  P  .  P  .  P  .  .  .  P  .  P  .  .  .  P  .  P  .
       |  |     |     |        |     |        |     |
       v  v     v     v        v     v        v     v
result ঝুড়ি: [2, 3, 5, 7, 11, 13, 17, 19]

P = prime (তালিকায় গেল),  . = composite (বাদ)

লক্ষ করো — প্রতিটা num-এর জন্য 013-এর পুরো √num check আলাদাভাবে চলছে (নিচে দেখব এটাই খরচের জায়গা)।

6. Example input and output

primes_upto(N)
-----------------------------------------
primes_upto(20) -> [2, 3, 5, 7, 11, 13, 17, 19]
primes_upto(2)  -> [2]            (সবচেয়ে ছোট prime)
primes_upto(1)  -> []            <-- 2-এর নিচে কোনো prime নেই
primes_upto(0)  -> []
primes_upto(13) -> [2, 3, 5, 7, 11, 13]   (13 নিজেও ধরা পড়ে, ≤ N)

দুটো edge case: N < 2 হলে খালি তালিকা (2-ই সবচেয়ে ছোট prime, তার নিচে কেউ নেই), আর N নিজে prime হলে সে-ও তালিকায় (যেমন N = 13)। তাই loop-এ N পর্যন্ত ধরা (range(2, N+1)) জরুরি।

7. Brute force thinking

সবচেয়ে সরল — 013-এর is_prime কে loop-এ বসিয়ে প্রতিটা সংখ্যা যাচাই:

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True

def primes_upto_brute(N):
    return [num for num in range(2, N + 1) if is_prime(num)]

একদম পরিষ্কার, 013 জানলে এক মিনিটে লেখা। 2 থেকে N পর্যন্ত প্রতিটা সংখ্যায় is_prime ডাকছি, যারা prime তাদের তালিকায় নিচ্ছি। ছোট-মাঝারি N-এ (যেমন 10⁴, 10⁵) এটাই যথেষ্ট।

8. Why brute force may be slow

প্রতিটা সংখ্যার জন্য আলাদা √num check — মোট খরচ যোগ হয়ে বড় হয়:

• N পর্যন্ত প্রতিটা সংখ্যায় ≈ √num কাজ, মোট ≈ √2 + √3 + ... + √N ≈ O(N√N)। N = 10⁶ হলে ≈ 10⁹ কাজ — ধীর, প্রায় TLE।

N = 1000000 হলে:
  এক-এক করে check : O(N√N) ≈ 10^9 কাজ      -> ধীর
  Sieve (015)     : O(N log log N) ≈ ~3×10^6 -> অনেক দ্রুত

কোথায় অপচয়? একই composite সংখ্যা (যেমন 30) আমরা বারবার "ভাগ যায় কিনা" পরীক্ষা করি — অথচ 30 যে 2, 3, 5-এর গুণিতক, সেটা একবার জানলেই হতো। এই বারবার পরীক্ষার অপচয়ই Sieve-এর জন্ম দেয়: prime খুঁজে না বের করে, composite-দের একসাথে কেটে ফেলা (015-এ পুরোটা)। এই note-এর সবচেয়ে দামি উপলব্ধি এটাই।

9. Better thinking

দুটো স্তরে উন্নতি:

(ক) ছোট optimization — 2 আলাদা, পরে শুধু বিজোড়: 2 ছাড়া সব জোড় সংখ্যা বাদ, তাই check করার সংখ্যা প্রায় অর্ধেক:

def primes_upto(N):
    if N < 2:
        return []
    result = [2]
    for num in range(3, N + 1, 2):     # শুধু বিজোড়
        if is_prime(num):
            result.append(num)
    return result

(খ) আসল বড় লাফ — Sieve (পরের problem 015): এক-একটা সংখ্যা check না করে, 2 থেকে শুরু করে প্রতিটা prime-এর সব গুণিতক একসাথে কেটে ফেলা; যারা বেঁচে থাকে তারাই prime। এটা O(N log log N) — N বড় হলে আকাশ-পাতাল দ্রুত। 014 হলো সেই দরজার সামনে দাঁড়ানো; ভেতরে ঢুকব 015-এ।

10. Thinking tweak

মূল মোচড় দুই ভাগে:

• এই problem-এর জন্য: "একটা সংখ্যা prime?" উত্তর জানা থাকলে "সব prime?" শুধু একটা loop + জড়ো করা — নতুন কিছু ভাবার নেই, পুরোনো হাতিয়ার পুনর্ব্যবহার।
• পরের দিকে তাকানো tweak (আসল আহা): prime খুঁজো না — composite কেটে ফেলো। এক-একটা সংখ্যায় বারবার ভাগের পরীক্ষা চালানোর বদলে, প্রতিটা prime-এর গুণিতক একবারে দাগিয়ে দাও; যা অদাগি থাকে তা-ই prime। এই দৃষ্টিভঙ্গি-বদল (search → mark) Sieve-এর প্রাণ, আর precompute-জাতীয় বহু problem-এ ফিরবে।

এই note-এর মূল শিক্ষা তাই একটা সমাধান নয়, একটা প্রশ্ন: "একই কাজ কি বারবার করছি? তবে কি একসাথে করা যায়?"

11. Step-by-step dry run

N = 10 দিয়ে Section 9-এর version (2 আলাদা, পরে বিজোড়) হাতে চালাই:

ধাপ	num	is_prime(num)?	result (পরে)
শুরু	—	—	[2]
1	3	True (3 prime)	[2, 3]
2	5	True	[2, 3, 5]
3	7	True	[2, 3, 5, 7]
4	9	False (9 = 3×3)	[2, 3, 5, 7]

loop range(3, 11, 2) শেষ (3, 5, 7, 9 দেখা হলো)। চূড়ান্ত [2, 3, 5, 7] — ঠিক 10 পর্যন্ত সব prime। লক্ষ করো 9-এ is_prime False ফিরিয়েছে (013-এর √9 check-এ 3 ভাগ করল), তাই বাদ। আর জোড় সংখ্যা (4, 6, 8, 10) আমরা দেখিইনি — 2 আগেই তালিকায়, বাকি জোড়রা prime নয় বলে।

12. Python solution

def is_prime(n):
    """013-এর √n prime check (পুনর্ব্যবহার)।"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True


def primes_upto(N):
    """2 থেকে N পর্যন্ত সব prime-এর তালিকা (repeated check)।"""
    if N < 2:
        return []
    result = [2]
    for num in range(3, N + 1, 2):     # 2 আলাদা, এরপর শুধু বিজোড়
        if is_prime(num):
            result.append(num)
    return result


def primes_upto_brute(N):
    """একই উত্তর, সরল সব-সংখ্যা check — যাচাইয়ের জন্য।"""
    return [num for num in range(2, N + 1) if is_prime(num)]


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert primes_upto(20) == [2, 3, 5, 7, 11, 13, 17, 19]
assert primes_upto(2) == [2]          # সবচেয়ে ছোট prime
assert primes_upto(1) == []           # 2-এর নিচে কিছু নেই
assert primes_upto(0) == []
assert primes_upto(-5) == []
assert primes_upto(13) == [2, 3, 5, 7, 11, 13]   # N নিজে prime, ধরা পড়ে

# দুই পদ্ধতি সব N-এ মেলে কিনা
for N in range(0, 100):
    assert primes_upto(N) == primes_upto_brute(N)

# 30 পর্যন্ত prime সংখ্যা ঠিক 10টা
assert len(primes_upto(30)) == 10

print(primes_upto(20))   # [2, 3, 5, 7, 11, 13, 17, 19]
print(primes_upto(2))    # [2]
print(primes_upto(1))    # []
print("সব test pass!")

13. Line-by-line explanation

def is_prime(n):
    ...

013-এর সেই √n prime check, হুবহু পুনর্ব্যবহার — 2 আলাদা, জোড় বাদ, তারপর বিজোড় ভাজক দিয়ে √n পর্যন্ত। 014-এর পুরো সঠিকতা এই function-এর উপর দাঁড়িয়ে।

    if N < 2:
        return []

N 2-এর নিচে হলে কোনো prime নেই — খালি তালিকা ফেরাই (edge case)।

    result = [2]
    for num in range(3, N + 1, 2):
        if is_prime(num):
            result.append(num)

2-কে আগে তালিকায় রাখি (একমাত্র জোড় prime), তারপর range(3, N+1, 2) দিয়ে শুধু বিজোড় সংখ্যা (3, 5, 7...) ঘুরি — জোড়রা 2 ছাড়া prime নয় বলে বাদ। প্রতিটা prime হলে তালিকায় যোগ। N + 1 দিয়ে N-কেও ধরছি (N নিজে prime হলে যেন বাদ না পড়ে)।

def primes_upto_brute(N):
    return [num for num in range(2, N + 1) if is_prime(num)]

তুলনার version — কোনো 2-আলাদা চাল নয়, সরাসরি 2 থেকে N সব সংখ্যা check। ধীর হলেও সহজ, তাই reference হিসেবে ভালো।

for N in range(0, 100) loop দুই পদ্ধতিকে 100টা N-এ মিলিয়ে যাচাই করে (সোনার নিয়ম)। সব মিললে সব test pass!।

14. Output walkthrough

চালালে ছাপবে:

[2, 3, 5, 7, 11, 13, 17, 19]
[2]
[]
সব test pass!

তিনটা লাইন তিনটা print থেকে: primes_upto(20) → 20 পর্যন্ত 8টা prime, primes_upto(2) → শুধু [2], primes_upto(1) → খালি তালিকা (edge case)। তার আগে সব assert — নির্দিষ্ট কেস, 0..99 জুড়ে দুই পদ্ধতির মিল, আর 30 পর্যন্ত গোনা — চুপচাপ pass করেছে। শেষ লাইন সব test pass! মানে তালিকা সব ক্ষেত্রে সঠিক।

15. Time complexity

O(N√N) — 2 থেকে N পর্যন্ত প্রতিটা সংখ্যায় ≈ √num কাজ (013-এর check), যোগ করলে প্রায় N × √N। N = 10⁴-এ ঠিকঠাক, কিন্তু N = 10⁶-এ (~10⁹ কাজ) ধীর। তুলনায় Sieve (015) O(N log log N) — অনেক দ্রুত। (2-আলাদা optimization ধ্রুবক গুণনীয়ক অর্ধেক করে, কিন্তু Big-O একই থাকে।)

16. Space complexity

O(π(N)) — যেখানে π(N) মানে N পর্যন্ত prime সংখ্যা (output তালিকার আকার)। prime check নিজে O(1) extra space নেয়; মূল জায়গা যায় ফলাফল তালিকায়। (সব prime ফেরত দিতেই হবে, তাই এটা অনিবার্য।)

17. Common mistakes

1. range(2, N) দিয়ে N বাদ — N নিজে prime হলে (যেমন 13) তালিকায় থাকা উচিত; range(2, N+1) লাগে, নাহলে শেষ prime ফসকায়।
2. N < 2-এ খালি তালিকা না দেওয়া — primes_upto(1) বা primes_upto(0) যেন [] ফেরায়; না হলে loop বা index-এ গোলমাল।
3. is_prime-এ 1 বা 2-এর ভুল ছড়িয়ে পড়া — 013-এর check-এ 1-কে prime ধরলে বা 2-কে বাদ দিলে, এখানে পুরো তালিকা ভুল হবে। ভিত্তি function ঠিক রাখো।
4. বড় N-এ এই পদ্ধতিতে আটকে থাকা — N বিশাল হলে repeated check TLE দেবে; তখন Sieve (015)-এ যাও। "এক-এক করে check" সবসময়ের সমাধান নয়।
5. জোড় optimization-এ 2 ভুলে যাওয়া — শুধু বিজোড় loop করলে 2-কে আলাদা করে result-এ আগে রাখতে ভুলো না, নাহলে 2 তালিকা থেকে বাদ পড়বে।

18. Harder problems that inherit this idea

• 015 — Sieve of Eratosthenes (এই repo) — এই problem-এর সরাসরি উত্তর-উন্নয়ন: এক-এক করে check না করে composite একসাথে কেটে ফেলা, O(N log log N)। সম্পর্কিত: CP-Algorithms — Sieve (https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html)।
• LeetCode — Count Primes (https://leetcode.com/problems/count-primes/) — N পর্যন্ত কতগুলো prime (গোনা); বড় N বলে এটা মূলত Sieve দিয়েই সমাধান করতে হয় — এই problem থেকে Sieve-এ যাওয়ার তাগিদ।
• CSES — Counting Divisors (https://cses.fi/problemset/task/1713) — অনেকগুলো সংখ্যার উপর কাজ; এখানেও "একসাথে precompute" (sieve-জাতীয়) চিন্তা লাগে।

19. Pattern learned

Repeated prime check — একটা নির্ভরযোগ্য is_prime থাকলে, loop-এ বসিয়ে 2..N সব prime জড়ো করা। বড় শিক্ষা: একই check বারবার চালালে অপচয় হয় (O(N√N)) — আর এই উপলব্ধিই "search বদলে mark" (Sieve) দৃষ্টিভঙ্গির জন্ম দেয়। তাই এই problem আসলে একটা সেতু: brute থেকে precompute-এ ভাবতে শেখা।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "all primes up to N = 013-এর is_prime কে range(2, N+1)-এ loop করে জড়ো করো (2 আলাদা রাখলে বাকি বিজোড়-only)। N < 2 হলে []; N নিজে prime হলে ধরতে N+1। কিন্তু এটা O(N√N) — N বড় হলে Sieve (015)-এ যাও: prime খুঁজো না, composite কাটো।"

আগের ধাপ → 013 — Check Prime (যে check বারবার ডাকছি)। পরের ধাপ → 015 — Sieve of Eratosthenes (এই অপচয় কাটিয়ে একসাথে কেটে ফেলা)।

ফিরে দেখা: এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য রাখা; "asked by Google/Amazon" এমন দাবি করা হয়নি — বরং "common interview pattern" হিসেবে লেখা।