finding out the divisors of a number

Question

What is the most optimized approach of finding out the number of divisors of a number,such that the divisors have at least the digit 3 in it?

e.g. 21=1,3,7,21

therefore only one divisor has the digit 3 in it.

e.g. 62=1,2,31,62

therefore only one divisor has the digit 3 in it and i.e. 31

EDIT-i realized that the best way to do this woulds be to find out all the factors of a number and check for the factors containing the digit 3.

the best way to find out the factors :

Getting Factors of a Number

What is the best way to get all the divisors of a number?

Related Post : http://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number — skjcyber, Oct 06 '13 at 10:49
@Bunyip i don't have to calculate the number of divisors here.SEE THE CONSTRAINT(divisors should have the digit 3 present in it). — RKTSP, Oct 06 '13 at 10:56
Missing something here why 1*3*7 instead of 3*7, or 1*1*7*3 or 1*7*1*3? — Tony Hopkinson, Oct 06 '13 at 11:07
@Bunyip, said related post ie find the divisors and then filter them for ones with a 3 in them. — Tony Hopkinson, Oct 06 '13 at 11:10
What is the input range? If it's small enough, build a table that contains all 'valid' numbers and check if your number can be divided by each. That table would go [3, 13, 23, 31, 32, 34, ...] (where multiples of earlier numbers can be omitted straight away). — Jongware, Oct 06 '13 at 11:32
@SteveJessop how do i find out all the divisors in the most optimized way? — RKTSP, Oct 06 '13 at 11:32
@Jarod42 for 64 i want 1,2,4,8,16,32,64.But number of such divisors will be 1,i.e. 32 — RKTSP, Oct 06 '13 at 11:42

Jongware · Answer 1 · 2013-10-06T13:10:30.653

Here is an expansion on my take. It first checks if there is a possible factor in the list div3. If not, it adds candidates up to number/2, skipping values that already could be factored according to this list, so '37' and '43' get added, but not '36' or '39'.

The above part should be considered "setup". If you know the input constraints (a maximum input value), you can calculate the vector div3 once, then store it inside the program.

If the list div3 is up to date, the input should be factored into one of these numbers. If it can't then none of its factors contain a '3'. If it can, this shows the remainder, which can be factored further using conventional methods.

I consider this "optimized" because the constraint "any factor should contain a '3'" is checked first. Only if any valid factor is found, you need to calculate all the others.

My first program using <vector> and its ilk, so be gentle in your comments :-)

(Edit) I now notice the factor checking loop goes over the entire div3 vector. Of course, it only needs to go up to number/2. Left as an exercise to the reader.

(Additional edit) find3 is here a reverse iterator. For some reason that seemed appropriate, but I can't recall why I thought so :) If checking up to and including number/2, you need to change it to a regular forward iterator.

#include <iostream>
#include <vector>

using namespace std;

int contains_3 (int value)
{
    while (value && (value % 10) != 3)
        value /= 10;
    return value;
}

int main (int argc, char **argv)
{
    int number, found_flag, last_div3, adjust, adjust_digit;
    vector<int> div3;
    vector<int>::reverse_iterator find3;
    vector<int>::iterator it;

    // a little seeding
    div3.push_back(3);
    div3.push_back(13);
    div3.push_back(23);

    if (argc != 2)
        return -1;

    number = atoi (argv[1]);
    found_flag = 0;

    // do we need to expand div3?
    last_div3 = div3.back();

    while (last_div3 * 2 < number)
    {
    //  if this number contains a '3' in any other place than the last,
    //  simply increment it
        if ((last_div3 % 10) != 9 && contains_3(last_div3/10))
        {
            last_div3++;
        } else
        {
            // no? then simply pick the next multiple of 10 and add 3
            last_div3 /= 10;
            last_div3++;
            last_div3 *= 10;
            if (!contains_3(last_div3))
                last_div3 += 3;
        }
    //  check if it should be in the list
        for (it = div3.begin() ; it != div3.end() && (last_div3 % *it); ++it) ;
        if (it == div3.end())
        {
            div3.push_back(last_div3);
        }
    }

    cout << "list is now: ";
    for (it = div3.begin() ; it != div3.end(); ++it)
        cout << ' ' << *it;
    cout << endl;

    for (find3 = div3.rbegin(); !found_flag && find3 != div3.rend(); find3++)
    {
        if (!(number % *find3))
        {
            cout << "candidate: " << *find3 << ", remaining to sieve: " << number/(*find3) << endl;

            found_flag++;
        }
    }

    if (!found_flag)
        cout << "None found" << endl;

    return 0;
}

Hah! I forgot the obvious simple case for *n* where *n* itself contains a '3' (and its corresponding factor is '1'). So you can use my `contains_3` routine as the first one on the input, and if it does it fulfills the constraint. — Jongware, Oct 06 '13 at 13:59

finding out the divisors of a number

1 Answers1