# Get numbers that have only 2,3 and 5 as prime factors

I am given an integer N. I have to find first N elements that are divisible by 2,3 or 5, but not by any other prime number.

N = 3
Results: 2,3,5
N = 5
Results: 2,3,5,6,8


Mistake number = 55.. 55/5 = 11.. 11 is prime number.. so means that it divides by any other prime number and doesn't counts in..

I guess there is need of recursive function,but I cant imagine what would algorithm look like

I was sent here from stackoverflow.

They gave me advice.. 2^i*3^j*5^k , for i,j,k = 0,1,2... , but it won't give an ordered array, because 2*2 < 2*3 .. and so on

I am trying to get this work in C++

The algorithm in this answer, in the end, is the same as the one in Bill Dubuque's answer, but I hope to be more elaborate and describe how one could arrive at the algorithm. Let's frame the problem as that of building the list of all such numbers in ascending order, i.e., each time adding to the list the smallest number that is not already in it.

First, note that all the numbers you want are of the form $2^i3^j5^k$, where $i, j, k$ are nonnegative integers. This means that after the first number $1$ (corresponding to $i = j = k = 0$), each "next" number can be obtained by multiplying some number already generated in the list, by either $2$, or $3$ or $5$.

So you start the list with the first number, $1$. To find the next number, you have three choices: multiply the number $1$ by either $2$, or $3$, or $5$. Since you want the smallest result, you pick $2$, and your list becomes $[1, 2]$.

Now you can no longer multiply $1$ by $2$ to get a new number, it is "used up". Your three choices now are: multiplying $1$ by $3$, multiplying $1$ by $5$, or multiplying $\color{red}{2}$ by $2$. The smallest result is from multiplying $1$ by $3$, so you add the result to the list, which becomes $[1, 2, 3]$.

Now you can no longer multiply $1$ by $3$, it is "used up" for multiplication by $3$. The smallest number you can multiply by $3$ is the next number, $2$. Your three choices now are: multiplying $\color{red}{2}$ by $2$, multiplying $\color{red}2$ by $3$, and multiplying $1$ by $5$. You pick the smallest result, which corresponds to multiplying $2$ by $2$ and gives you $4$ which you add to the list, and now $2$ is also used up for multiplication by $2$ and for multiplication by $2$ you have to go to the next number in the list, namely $3$.

In general, you always have three choices: one number that you can multiply by $2$, another that you can multiply by $3$, and another that you can multiply by $5$. You pick whichever of these three choices gives the smallest result, and update the choice ("advance the pointer") for 2 or 3 or 5, whichever you chose.

The first few steps worked out explicitly:

List is $[1]$. Choice for 2 is $1$, choice for 3 is $1$, choice for 5 is $1$. (Choose multiplication by 2.)

List is $[1, 2]$. Choice for 2 is $2$, choice for 3 is $1$, choice for 5 is $1$. (Choose multiplication by 3.)

List is $[1, 2, 3]$. Choice for 2 is $2$, choice for 3 is $2$, choice for 5 is $1$. (Choose multiplication by 2.)

List $[1, 2, 3, 4]$. Choice for 2 is $3$, for 3 is $2$, choice for 5 is $1$. (Choose multiplication by 5.)

List is $[1, 2, 3, 4, 5]$. Choice for 2 is $3$, for 3 is $2$, for 5 is $2$. (Choose multiplication by 2.)

List is $[1, 2, 3, 4, 5, 6]$. Choice for 2 is $4$, for 3 is $3$ (note that we updated this also), for 5 is $2$. (Choose multiplication by 2.)

List is $[1, 2, 3, 4, 5, 6, 8]$. Choice for 2 is $5$, for 3 is $3$, for 5 is $2$. (Choose multiplication by $3$.)

List is $[1, 2, 3, 4, 5, 6, 8, 9]$. Choice for 2 is $5$, for 3 is $4$, for 5 is $2$.

List is $[1, 2, 3, 4, 5, 6, 8, 9, 10]$. Choice for 2 is $6$, for 3 is $4$, for 5 is $3$.

List is $[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]$. Choice for 2 is $8$, for 3 is $5$, for $5$ is $3$.

List is $[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15]$. Choice for 2 is $8$, for 3 is $6$, for $5$ is $4$.

In code, you could implement it as a growing array, with three array indices pointing to the choices for 2, 3, and 5. Here is a complete working Python program (time.sleep is to keep it slow enough to see the output):

import time
num = [1]
c2 = c3 = c5 = 0

while True:
next = min(2*num[c2], 3*num[c3], 5*num[c5])
num.append(next)
print num
if next == 2*num[c2]: c2 += 1
if next == 3*num[c3]: c3 += 1
if next == 5*num[c5]: c5 += 1
time.sleep(0.5)

• I've got solution.. @binn, too simple and effective Sep 17, 2012 at 22:00
• @waplet: That is not at all efficient, plus it's the obvious boring solution. :-) And this one is about the same (or fewer) number of lines of code as that, so it isn't really harder to code. Anyway, whatever works for you. Sep 18, 2012 at 1:57
• Yeah, i found it easy to implement .. too :) Thank you also.. I guess this one is more faster , though? Sep 18, 2012 at 16:06

Hint $\$ There is a very simple recursive algorithm, e.g. the final $\color{#C00}\to$ below is calculated as follows.

$\ \ 1_{2,3,5}\to 1_{3,5} 2_2\to 1_5 2_{2,3} 3\to 1_5 2_{3} 3_2 4\to 1\, 2_{3,5} 3_2 4\, 5\to 1 2_{5} 3_3 4_2 5\,6\color{#C00}\to 1 2_{5} 3_3 4\, 5_2 6\,8\to\, \cdots$

The term $\:1 2_{5} 3_3 4_2 5\,6\:$ on the left of the $\color{#C00}\to$ means that we have computed the initial sequence $\:1\,2\,3\,4\,5\,6,\:$ where the subscript $5$ on $2$ means that $2\cdot 5$ is the next multiple of $5$ to insert, similarly $3\cdot 3$ and $4\cdot 2$ are the next multiples of $3$ and $2$ to be inserted. Therefore the next term must be $\rm\:min(2\cdot 5, 3\cdot 3, 4\cdot 2) = 8.\:$ Since $8$ is not already at the end, we append it, then we bump the subscript $2$ from $4$ to the next term $5$, indicating that $2\cdot 5$ is the next multiple of $5$. Then recurse.

This can be implemented elegantly in a functional programming language using (lazy) streams for the multiples of $2,3,5$.

• Quite hard to understand, for me who don't have english as native language :S Sep 17, 2012 at 12:18
• @waplet What is not clear? Sep 17, 2012 at 13:01

Make a loop over numbers i. Check the numbers one at a time, it doesn't need to be recursive.

If you want, you can use a nice recursive algorithm f(i) which is true or false depending on whether the number i should be allowed into the list.
f(i):
if i == 1: return true
else if i % 2 == 0: return f(i/2)
else if i % 3 == 0: return f(i/3)
else if i % 5 == 0: return f(i/5)
else: return false

Start the loop at 2, otherwise this function will wrongly allow 1 into the list.

• Oh thanx, got to check it :) Sep 17, 2012 at 12:16
• This algorithm may function, but it will run in exponential time; by the very definition of the problem, you'll need to loop through $2^a3^b5^c$ numbers, where $a+b+c = N$ and $2^a\leq3^b\leq5^c$, to return the required N results. You will additionally need to recurse deeply through all numbers of factorization $2^a3^b5^cq$ where $q$ is some other prime or product of primes. As a computational strategy, this is the worst possible thing I can think of to recommend. Sep 17, 2012 at 15:07
• This was the most simplest, but the most effective . Thank you:) Sep 17, 2012 at 16:33

I'd build it up from the prime factorization. You're looking for numbers with a prime factorization of the form $2^a3^b5^c$. Thus, you can simply start with an a, b, and c of zero, and work along the following pseudocode algorithm:

do
{
if(2^(a+1) > 3^(b+1))
if(3^(b+1) > 5^(c+1))
{
increment c
b = 0
a = 0
}
else
{
increment b
a = 0
}
else
increment a

}
while(results.count < N) //should loop exactly N times

• Didn't work out.. Dunno what i have done wrong Sep 17, 2012 at 16:17

I solve this kind of situation with this:

 function getIdealNums($$l,$$r) { $$numbers = []; for ($$x=0; $$x <= 2*pow(10, 5);$$x++) { for ($$y=0;$$y <= 2*pow(10, 5); $$y++) { number = pow(3, x)*pow(5, y); if (l <= number) { if (number <= r) { array_push(numbers, number); } else { break; } } } } return count($$numbers); } 

I get similar type of question on competitive programming, although I'm beginner, my code is not much optimized but I think it will help.

// 1 2 3 4 5 6 8 9 10 12 14 15 16 18 20 21......etc//
// 1 2 3 4 5 6 7 8 9  10 11 12 13 14 15 16......etc//

#include<iostream>
using namespace std;

int main()
{
int n;
int size = 1000;
int arr[size];
int count = 1;
int str = 1;
int temp = 0;

cin>>n;
temp = n;

while(count <= temp)
{
//cout<<"looping count : "<<count<<endl;

if(temp == 1)
{
arr[count] = str;
}
if(count == 1)
{
arr[count] = str;
}
else if(count > 1)
{
str += 1;

if(str % 2 == 0 || str % 3 == 0 || str % 5 == 0)
{
arr[count] = str;
}
else
{
str += 1;
arr[count] = str;
}

}

count += 1;
}

for(count = 1; count <= temp; count++)
cout<<"Array at "<<count<<" "<<arr[count]<<endl;

cout<<"End str : "<<str<<endl;

return 0;
}