Interactive Programming Education Platform

Logic Practice

In this post, we will explore the concept of Polydivisible Numbers in the C++ programming language, including its algorithm, pseudocode, and illustrative examples.

What is the Polydivisible Number in C++?

A number is considered polydivisible if it satisfies specific divisibility criteria based on its prefixes. For a whole number N with k digits, the first digit must be divisible by 1, the first two digits by 2, the first three by 3, and so forth.

For instance, the number 123 is polydivisible because 1 ÷ 1 = 1, 12 ÷ 2 = 6, and 123 ÷ 3 = 41. To verify this property, we can iteratively extract the prefixes of a number and validate their divisibility by their respective lengths in C++.

A number is considered polydivisible if each of its prefixes meets a special divisibility property. The following occurs when a number is polydivisible:

✅ The first number, which is the most significant, is divisible by 1.
✅ The first two numbers added together are divisible by two.
✅ The first three numbers added together are divisible by three.
✅ The procedure keeps going until the entire number is confirmed.

In simpler terms, consider a number N with digits d1, d2,…, dk. The prefix formed by the first i digits, where i ranges from 1 to k, denoted as Pi = d1d2…di, should be divisible by i.

For Example:

1: 1÷1=1 (valid).

12: 1÷1=1, 12÷2=6 (valid).

123: 1÷1=1, 12÷2=6, 123÷3=41 (valid).

Dividing 1 by 1 equals 1, dividing 12 by 2 equals 6, dividing 123 by 3 equals 41, and dividing 1234 by 4 equals 308.5 (which is not a valid division).

Input: N=768

Output: 768 is a polydivisible number.

For instance, in cases where p is greater than 1 and less than or equal to the total number of digits in the given number, then every p-th digit must be divisible by p.

Input: 42587

Output: There is no polydivisible integer equal to 42587.

The reason is that the value of p=3 is not considered a polydivisible number due to its failure to meet the required criteria. Specifically, when examining the initial three digits of the number, 425 is an example of a number that is not divisible by 3.

Algorithm:

✅ All of the digits of the specified number N will be removed and stored.
✅ In order to store each digit, we'll utilize an array . Using modulo function, we will extract the digits and divide each number by 10.
✅ Since the array's stored digits will be in reverse order, we will use the reverse function to flip the array.
✅ Check whether each p digit is divisible by p by iterating through for loop. A number is considered polydivisible if it holds true for all values of p up until p equals the number of digits in the provided number.
✅ Using for loop, we will now determine whether or not the number is polydivisible.

Pseudo code:

Example


function isPolydivisible(number)
    convert number to string numStr
    set length to size of numStr
    for i from1 to length do
        set prefix to the first i characters of numStr, converted to integer
        if prefix mod i ≠ 0 then
            return false
        end if
    end for
    return true
end function
main
    input number
    call isPolydivisible(number) and store result
    if result is true then
        print "The number is polydivisible."
    else
        print "The number is not polydivisible."
    end if
end main

Example:

Let's consider an illustration to demonstrate the concept of polydivisible numbers in the C++ programming language.

Example


#include <iostream>
#include <string>
using namespace std;
// Function to check if a number is polydivisible
bool isPolydivisible(long long number) {
    string numStr = to_string(number);
    int length = numStr.size();
    for (int i = 1; i <= length; ++i) {
        // Extract the prefix of length i
        long long prefix = stoll(numStr.substr(0, i));
        // Check if the prefix is divisible by i
        if (prefix % i != 0) {
            return false; // Not polydivisible
        }
    }
    return true; // Polydivisible
}
int main() {
    long long number;
    cout << "Enter a number to check if it is polydivisible: ";
    cin >> number;
    if (isPolydivisible(number)) {
        cout << number << " is a polydivisible number." << endl;
    } else {
        cout << number << " is not a polydivisible number." << endl;
    }

    return 0;
}

Output:

Output


Enter a number to check if it is polydivisible: 34
34 is a polydivisible number.
Enter a number to check if it is polydivisible: 42587
42587 is not a polydivisible number.

Explanation:

✅ Input Conversion: In order to make prefix extraction simple, the integer is transformed into a string.
✅ Prefix extraction: Prefix extraction is the process of extracting prefixes of increasing lengths using substr.
✅ Divisibility Check: After each prefix has been transformed back into an integer, its length is compared to its divisibility.
✅ Result: The number is polydivisible if every prefix satisfies the divisibility criterion.

Conclusion:

To sum up, polydivisible numbers represent a fascinating mathematical idea that blends understanding of number composition and divisibility principles. These special numbers offer an intriguing puzzle for mathematical investigation and programming, offering a unique opportunity to explore rules based on prefixes and divisibility. By systematically checking a number's prefixes and confirming if they meet the divisibility criteria, one can efficiently ascertain the polydivisibility of a number using the C++ programming language. Beyond demonstrating the application of programming in resolving mathematical challenges, this concept enriches our comprehension of number characteristics and divisibility constraints. Delving into such subjects nurtures the enhancement of algorithmic thinking abilities and logical deduction skills.

Polydivisible Number In C++