Prime Numbers (ප්‍රථමක සංඛ්‍යා). සරලවම කිව්වොතින් 1 හැර 1 නුත් එම සංඛ්‍යාවෙනුත් පමණක් බෙදෙන සංඛ්‍යා තමයි Prime Numbers කියල කියන්නේ. උදාහරණ විදිහට 2,3,5,7,11,13,17 … මේ වගේ සංඛ්‍යා ගන්න පුළුවන්.

හොඳයි අද අපි බලන්නේ මොකක් හරි සංඛ්‍යාවක් Prime Number එකක් ද නැත්ද කියල නිර්ණය කර ගන්න පොඩි Program එකක් හදා ගන්නේ කොහොමද කියන එකයි.

හිතමු අපිට ලැබෙන සංඛ්‍යාව N කියල. අපිට කරන්න තියෙන්නේ මෙන්න මෙහෙම දෙයක් .
1 සිට N දක්වා තියන සංඛ්‍යා වලින් 1 හා N හැර වෙනත් මොකක් හරි සංඛ්‍යාවකින් N ව ඉතිරි නැතිව බෙදුනොතින් N Prime Number එකක් නෙවෙයි., එහෙම නොවේ නම්, ඒ කියන්නේ 1 හා N හැර ඒ අතර තියන එකදු සංඛ්‍යාවකින්වත් N ව ඉතුරු නැතිව බෙදුනේ නැත්නම් N Prime Number එකක්.

for i = 2 to N-1
    if i divides N
        N is not a Prime

ඉතින් මෙතැනදී අපිට තව ටිකක් හිතන්න පුළුවන්. අපි N – 1 දක්වා තියන සියලුම සංඛ්‍යා පරික්ෂා කරන්න ඕනෙද ? නෑ නේද ? මොකද N / 2 ට වඩා විශාල සංඛ්‍යාවකින් කිසිවිටකත් N ව ඉතුරු නැතුව බෙදෙන්න විදිහක් නෑ. ඒක පැහැදිලි වෙන්න මෙහෙම කියන්නම්. N = 12 නම් N ව බෙදෙන විශාලම සංඛාව 6. ඉ වගේම තමයි 6 ට වඩා වැඩි සංඛාවක ගුණාකාරයක් විදිහට අපිට N ව ලියන්න බෑ . ඉතින් මේ නිසා අපි පරික්ෂා කිරීම N / 2 දක්වා පමණක් සිදු කිරීම ප්‍රමාණවත් වෙනවා.
ඒක නිසා අපිට අපේ program එක මෙන්න මේ විදිහට තව ටිකක් දියුණු කර ගන්න පුළුවන්.

for i = 2 to N/2
    if i divides N
        N is not a Prime

හොඳයි දැන් සැහෙන දුරකට අපේ program එකේ efficiency එක වැඩි කර ගත්ත. තවත් ටිකක් හිතුවොතින් අපිට තවදුරටත් මේ for loop එක run වෙන වාර ගාන අඩු කරගන්න පුළුවන්.

මෙහෙම හිතන්න N ව ඉතුරු නැතිව බෙදන මොකක් හරි සංඛ්‍යාවක් තියනවනම් අනිවාර්යෙන්ම බෙදුවහම ලැබෙන උත්තරෙත් N ව ඉතුරු නැතිව බෙදන සංඛ්‍යාවක් වෙනවා නේද ? ඒ කියන්නේ  N / a = b නම් a සහ b දෙකම N ගෙ සාධක වෙනව. හිතන්න N = 36 කියල. මන් N ගේ සාධක මේ විදිහට පෙන්නුම් කරන්නම්.

36 —- {1,36}  {2,18}  {3,12}  {4,9}  {6,6}  {9,4}  {12,3}  {18,2}  {36,1}

36 මේක දිහා හොඳින් බැලුවොතින් පෙනෙයි {6,6} ට කලින් සහ පසුව තියන සාධක යුගල් වල කිසිම වෙනසක් නෑ කියන එක (පිළිවෙල වෙනස් වෙලා විතරයි තියෙන්නේ). මන් මේ සමාන පාට වලින් දක්වල තියන යුගල් එක සමානයි.

36  —- {1,36}  {2,18}  {3,12}  {4,9}  {6,6}  {9,4}  {12,3}  {18,2}  {36,1}

නමුත් කලින් හදපු program එකේදී මේ සමහර සමාන යුගල් පවා දෙවරක් පරික්ෂා වෙනව නේද ?
කලින් වතාවේදී N / 2 දක්වා පරික්ෂා කරන නිසා {3,12} {4,9} කියන අවස්ථා නැවත පරික්ෂාවකට ලක්වෙනවා. ඉතින් මේක ඇත්තෙන්ම කාලය නාස්ති කිරීමක්. අපිට පුළුවන් මේ විදිහට නැවත නැවත දෙවරක් පරික්ෂා වෙන ඇතැම් අවස්ථා පවා මග හරවාගෙන කලින්ට වඩා තවත් efficiency එක වැඩි program එකක් හදාගන්න.

හොඳයි මෙතැනදී N / a = b සලකපුවහම a = 6 අවස්ථාවේදී b = 6 වෙනව. ඒ වගේම a , 6 ට අඩු වෙන සෑම අවස්ථාවකම අනිවාර්යෙන්ම b, 6 ට වැඩි අගයක් ගන්නවා. ඉතින් මේ විදිහට බලපුවහම අපිට මේ වගේ අදහසක් ගන්න පුළුවන්.

if    a = b    —>   a2 = n    — >     a = √n

if    a   a √n

if   a > b    —>   a > √n  and      b < √n

ඉතින් මේ විදිහට බැලුවහම අපිට for loop මගින් එක N වල වර්ගමූලය දක්වා  පරික්ෂා කරහම ඇති කියල තේරෙනවා නේද ? මොකද N වල වර්ගමුලයට කලින් හම්බුන හැම සධකයක්ම නැවතත් වර්ගමුලයට පසුව හම්බෙන එක තමා සිද්ද වෙන්නේ. ඉතින් අපිට අපේ program එක මේ විදිහට තවත් ටිකක් දියුණු කර ගන්න පුළුවන්

for i = 2 to sqrt(N)
    if i divides N
        N is not a Prime

ඉතින් මේ විදිහට අපිට running time එක අඩු කරගෙන අපේ target එකට යන්න පුළුවන් විදිහට අපි හදන algorithms දියුණු කර ගන්න පුළුවන්. මන් මෙතැනදී Pseudo-code විදිහට තේරුම් ගන්න පහසු විදිහට තමා ඉදිරිපත් කරලා තියෙන්නේ. ඉතින් අවශ්‍ය ආකාරයට කැමති programming language එකක් use කරලා මේ Prime Numbers check කරන algorithm එක implement කර ගන්න පුළුවන්.

දැන් එහෙමනම් C++ Programming Language එක පාවිච්චි කරලා මේ කියපු දේ implement කරන්නේ කොහොමද කියල බලමු.
මම මෙතැනදී පරික්ෂා කරන්න User input එකක් විදිහට ගන්න Integer එක n විදිහටත්, ඒ වගේම Prime number එකක්ද කියල දැනගන්න isPrime කියල Boolean variable එකකුත් පාවිච්චි කරනවා. මෙතැනදී සිද්ද කරන්නේ 2 සිට n ගේ වර්ගමුලය දක්වා තියන සංඛ්‍යා වලින් එකකදී හෝ එම සංඛ්‍යාව විසින් n ව ඉතුරු නැතිව බෙදනවද නැද්ද කියල බලන එකයි.
හොඳයි මන් එහෙනම් මේ විදිහට Program එක ඉදිරිපත් කරන්නම්.


int main()
{
  int n, i;
  bool isPrime = true;

  cout <> n;

  for(i = 2; i <= sqrt(n); i++)
  {
      if(n % i == 0)
      {
          isPrime = false;
          break;
      }
  }
  if (isPrime)
      cout << "This is a prime number";
  else
      cout << "This is not a prime number";

  return 0;
}

 මෙතනදි  අපි sqrt කියන function එකට call කරන නිසා  “math .h”  library එක include කරගන්න අමතක කරන්න එපා.

Advertisements