หาจำนวนจำนวนเต็ม x ในช่วง (1,N) ที่ x และ x+1 มีจำนวนตัวหารเท่ากันใน C++

สมมติว่าเรามีจำนวนเต็ม N เราต้องหาจำนวนจำนวนเต็ม 1 < x < N ซึ่ง x และ x + 1 มีจำนวนตัวหารบวกเท่ากัน ดังนั้นถ้า N = 3 ผลลัพธ์จะเป็น 1 เพราะตัวหารของ 1 คือ 1 ตัวหารของ 2 คือ 1 และ 2 และตัวหารของ 3 คือ 1 และ 3

เพื่อแก้ปัญหานี้ เราจะหาจำนวนตัวหารของทุกตัวเลขต่ำกว่า N และเก็บไว้ในอาร์เรย์ จากนั้นนับจำนวนจำนวนเต็ม x ที่ x และ x + 1 มีจำนวนตัวหารบวกเท่ากันโดยการรันลูป

ตัวอย่าง

#include <iostream> 
#include <cmath> 
#define N 100005 
using namespace std; 

int table[N], pre[N];

void findPositiveDivisor() {
    for (int i = 1; i < N; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                if (j * j == i)
                    table[i]++;
                else
                    table[i] += 2;
            }
        }
    }
    int ans = 0;
    for (int i = 2; i < N; i++) {
        if (table[i] == table[i - 1])
            ans++;
        pre[i] = ans;
    }
}

int main() {
    findPositiveDivisor();
    int n = 15;
    cout << "Number of integers: " << pre[n] << endl;
}

ผลลัพธ์

Number of integers: 2