ค้นหาจำนวนตัวหารของตัวเลขทั้งหมดในช่วง [1, n] ใน C++

ในปัญหานี้ เราได้รับตัวเลข N หน้าที่ของเราคือ หาจำนวนตัวหารของตัวเลขทั้งหมดในช่วง [1, n].

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

Input : N = 7
Output : 1 2 2 3 2 4 2

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาง่ายๆ คือเริ่มจาก 1 ถึง N และสำหรับทุกตัวเลขให้นับจำนวนตัวหารแล้วพิมพ์ออกมา

ตัวอย่างที่ 1

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <iostream>
using namespace std;
int countDivisor(int N){
   int count = 1;
   for(int i = 2; i <= N; i++){
      if(N%i == 0)
         count++;
   }
   return count;
}
int main(){
   int N = 8;
   cout<<"The number of divisors of all numbers in the range are \t";
   cout<<"1 ";
   for(int i = 2; i <= N; i++){
      cout<<countDivisor(i)<<" ";
   }
   return 0;
}

ผลลัพธ์

The number of divisors of all numbers in the range are 1 2 2 3 2 4 2 4

อีกวิธีในการแก้ปัญหาคือการใช้ค่าที่เพิ่มขึ้น สำหรับสิ่งนี้ เราจะสร้างอาร์เรย์ขนาด (N+1) จากนั้น เริ่มจาก 1 ถึง N เราจะตรวจสอบแต่ละค่า i เราจะเพิ่มค่าอาร์เรย์สำหรับทวีคูณทั้งหมดของ i ที่น้อยกว่า n

ตัวอย่างที่ 2

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#include <iostream>
using namespace std;
void countDivisors(int N){
   int arr[N+1];
   for(int i = 0; i <= N; i++)
      arr[i] = 1;
      for (int i = 2; i <= N; i++) {
         for (int j = 1; j * i <= N; j++)
            arr[i * j]++;
      }
      for (int i = 1; i <= N; i++)
         cout<<arr[i]<<" ";
}
int main(){
   int N = 8;
   cout<<"The number of divisors of all numbers in the range are \t"; countDivisors(N);
   return 0;
}

ผลลัพธ์

The number of divisors of all numbers in the range are 1 2 2 3 2 4 2 4