Algorithm to determine set of numbers which can be factorised as 2^p5^q

Question

I'm trying to write an algorithm that can return the set of positive integers that is less than an instance n and can be factorised as 2^p5^q. My maths is not the best, so I have no idea how I can determine whether a number can be factorised in this specific form...

Any help would be much appreciated :)

Answer 1

I have no idea how I can determine whether a number can be factorised in this specific form

Instead of testing whether a given number can be factorised and running through all numbers less than n, why not just generate them, e.g:

void findNumbers(int n)
{
    int p = 0;
    int power2 = 1; 
    while(power2 < n)
    {
        int q = 0;
        int power5 = 1;
        while(power5 * power2 < n)
        {
            printf("%d p = %d q = %d\n", power5 * power2, p, q);
            power5 *= 5;
            q++;
        }
        power2 *= 2;
        p++;
    }
}

Output for n = 500:

1 p = 0 q = 0
5 p = 0 q = 1
25 p = 0 q = 2
125 p = 0 q = 3
2 p = 1 q = 0
10 p = 1 q = 1
50 p = 1 q = 2
250 p = 1 q = 3
4 p = 2 q = 0
20 p = 2 q = 1
100 p = 2 q = 2
8 p = 3 q = 0
40 p = 3 q = 1
200 p = 3 q = 2
16 p = 4 q = 0
80 p = 4 q = 1
400 p = 4 q = 2
32 p = 5 q = 0
160 p = 5 q = 1
64 p = 6 q = 0
320 p = 6 q = 1
128 p = 7 q = 0
256 p = 8 q = 0

It just loops through every combination of p and q up to n.

If you want to exclude p = 0 and q = 0, just start the loops at 1 and set power2 = 2 and power5 = 5.