ដំណោះស្រាយលេខឡេឡេលេខកូដមិនល្អ


កម្រិតលំបាក មានភាពងាយស្រួល
គណិតវិទ្យា

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហានេះយើងត្រូវបានគេផ្តល់លេខហើយយើងត្រូវពិនិត្យមើលថាតើវាជាលេខអាក្រក់ឬអត់។
ដោយសារលេខអាក្រក់នោះគឺជាលេខវិជ្ជមានដែលកត្តាសំខាន់រួមមានតែ ២, ៣, ៥ ។
លេខ ១ ត្រូវបានចាត់ទុកជាលេខអាក្រក់។

ឧទាហរណ៍

6
true

ការពន្យល់៖ ៦ = ២ × ៣

14
false

ការពន្យល់៖ ៦ = ២ × ៣
១៤ មិនអាក្រក់ទេព្រោះវារួមបញ្ចូលកត្តាសំខាន់ ៧ ផ្សេងទៀត។

វិធីសាស្រ្ត

ពីសេចក្តីថ្លែងការណ៍បញ្ហាវាច្បាស់ណាស់ថាដើម្បីក្លាយជាលេខអាក្រក់វាមិនត្រូវមានលេខណាមួយទេ កត្តាសំខាន់ ផ្សេងទៀតជាង 2,3 និង 5 ។

យើងដឹងថារាល់លេខត្រូវបានបង្កើតឡើងដោយផលនៃអំណាចមួយចំនួននៃលេខបឋមមួយឬច្រើន (លើកលែងតែលេខ ១) ។ ដូច្នេះយើងអាចដាក់លេខទៅជាកត្តាសំខាន់របស់វាហើយមើលថាតើវាមានលេខបឋមក្រៅពី ២,៣ និង ៥ ឬអត់។

តាមកត្តាមានន័យថាបើលេខបឋមអាចចែកលេខបានទាំងស្រុងនោះវានឹងក្លាយជាកត្តាមួយនៃលេខពិសេសនោះ។ ដូច្នេះប្រសិនបើលេខអាចត្រូវបានបែងចែកដោយលេខ ២ យើងអាចចែកលេខដែលបានផ្តល់អោយដោយលេខ ២ ដូច្នេះយើងដកលេខ ១ នៃកត្តា ២ ។
ដូចគ្នានេះដែរយើងនឹងដកអំណាចទាំងអស់នៃកត្តា ៣ និង ៥ ចេញ។

ឥឡូវនេះវាច្បាស់ណាស់ថាប្រសិនបើលេខមានកត្តាបឋមក្រៅពី 2,3 និង 5 លេខដែលនៅសល់បច្ចុប្បន្ននឹងមិនស្មើនឹង 1 ទេ។
ដូច្នេះនៅពេលចុងក្រោយប្រសិនបើលេខក្លាយជាលេខ ១ នោះវាគឺជាលេខអាក្រក់ហើយយើងត្រឡប់ជាការពិតបើមិនដូច្នេះទេយើងមិនពិតទេ។

ការអនុវត្តន៍

កម្មវិធី C ++ សំរាប់ដំណោះស្រាយលេខអលឡេហ្សុកលេខអាក្រក់

#include <bits/stdc++.h>
using namespace std;

bool isUgly(int num) 
{	
  if(num<=0) return false;
   
  while(num%2==0) num/=2;
  while(num%3==0) num/=3;
  while(num%5==0) num/=5;
  
  if(num==1) return true; 
    else return false;
}

int main() 
{
    int num=8;
  
  if(isUgly(num))
    cout<<"true"<<endl;
  else
    cout<<"false"<<endl;

  return 0; 
}
true

ចាវ៉ាកម្មវិធីសំរាប់ដំណោះស្រាយលេខឡីលេខកូដមិនល្អ

import java.util.*;
import java.lang.*;


class UglyNumber
{  
   public static boolean isUgly(int num) 
   {
        if(num<=0) return false;
       
        while(num%2==0) num/=2;
        while(num%3==0) num/=3;
        while(num%5==0) num/=5;
        
        if(num==1) return true; 
        else return false;
        
    }
    
    public static void main(String args[])
    {
        int num=8;

        System.out.println(isUgly(num));
        
    }
}
true

ការវិភាគស្មុគស្មាញសម្រាប់ដំណោះស្រាយលេខឡៃកូដដែលមិនល្អ

ស្មុគស្មាញពេលវេលា

O (log (n))៖ យើងកំពុងបែងចែកលេខដោយ 2, 3 និង 5 ក្នុងខណៈពេលដែលរង្វិលជុំម្តងហើយម្តងទៀត។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលានឹងត្រូវបាន O (log (n)) ដែល n ជាលេខដែលបានផ្តល់។

ភាពស្មុគស្មាញនៃលំហ 

O (១)៖ យើងមិនប្រើកន្លែងទំនេរបន្ថែមទេដូច្នេះវាថេរ។