0 ကေန N အတြင္းမွာရွိေသာ prime numberမ်ားကို generateလုပ္ျခင္း

0 ကေန 100အတြင္းက prime numberေတြကို သိခ်င္တယ္ဆိုပါစို႔။ 0ကေန 100အထိ အကုန္လံုးကို primeဟုတ္မဟုတ္ လိုက္စစ္စရာမလိုပါဘူး။ ပိုျမန္ၿပီး လြယ္ကူတဲ့algorithmရွိပါတယ္။ Sieve of Eratosthenesလို႔ေခၚပါတယ္။

အရင္ဆံုး 2ကေနNအထိအကုန္လံုးကို primeလို႔ သတ္မွတ္ပါတယ္။ (boolean arrayကိုသံုးပါမယ္။ 2ကေနNအထိ trueေပးၿပီး 0နဲ႔1 ကfalseပါ)

2ကစၿပီးစဥ္းစားပါမယ္။

2ကprimeျဖစ္ေနတဲ့အတြက္ (true ျဖစ္ေနတဲ့အတြက္) 2ကို 1ထက္ႀကီးတဲ့number တစ္ခုနဲ႔ေျမႇာက္လို႔ရတဲ့တန္းဖိုးတိုင္းက primeမဟုတ္ေတာ့ပါဘူး။

အဲဒါေၾကာင့္ 4,6,8,10,...(<=Nအထိ) prime မဟုတ္ဘူးလို႔ သတ္မွတ္ပါတယ္။( 4,6,8,10,... ကိုfalseလုပ္ပါတယ္)

3ကလဲprimeျဖစ္ေနတဲ့အတြက္ (true ျဖစ္ေနတဲ့အတြက္) အေပၚကအတိုင္းလုပ္ပါတယ္။

အဲဒါေၾကာင့္ 6,9,12,15,...(<=Nအထိ) prime မဟုတ္ဘူးလို႔ သတ္မွတ္ပါတယ္။( 6,9,12,15,... ကိုfalseလုပ္ပါတယ္)

4အလွည့္က်ေတာ့ primeမဟုတ္တဲ့အတြက္ေက်ာ္သြားတယ္။(false ျဖစ္ေနတဲ့အတြက္)

ၿပီးေတာ့ 5,6,7,...square of Nမေက်ာ္ခင္အထိ အေပၚက အတိုင္းလုပ္ပါတယ္။ (for looping ပတ္လိုက္ရင္ရမယ္)

အေျဖက primeျဖစ္ေနေသးတဲ့numberေတြပါ။ (arrayထဲက trueျဖစ္ေနတဲ့ ေနရာေတြ)

အေပၚကအေၾကာင္းေတြက Competitive Programming 3စာအုပ္ထဲက Sieve of Eratosthenes: Generating List of Prime Numbersဆိုတဲ့အပိုင္းကို ဘာသာျပန္ၿပီးေရးထားတာ။

ဒီalgorithmက ပံုမွန္သံုးေနကprimeစစ္တဲ့algorithmကိုေျပာင္းျပန္လုပ္ထားတာ။ စားတာမပါဘဲ ေျမႇာက္တာပဲပါတယ္။

မေကာင္းတာက 100ကေန200အတြင္းက prime numberေတြရွာမယ္ဆိုလဲ 0ကေန200အထိရွာရတယ္။

အျမဲတမ္း0ကေနစရတယ္။

wikipediaကပံုကိုၾကည့္လိုက္ရင္ ပိုရွင္းမယ္ထင္တယ္။