"Least" common multiple of A and B, greater than C 
Least common multiple of $A$ and $B$ that is greater than $C$.

Is there any algorithm to find it without prime factorization?
 A: Sure, first find the least common multiple of A and B, which you can find by calculating:
$$\frac{|AB|}{\operatorname{gcd}(A,B)}$$
Then divide $C$ by the LCM.  If it divides evenly, then C is your answer, otherwise, the next highest multiple. So the result is:
$$L = AB/gcd(A,B)$$
$$C' ={ \left \lceil \frac{C}{L} \right \rceil } L$$
where $\left \lceil x \right \rceil$ is the smallest integer greater than or equal to $x$.
A: Hint $ $ Any common multiple $\,M\,$ is a multiple of their $\,{\rm lcm}\,\ m = AB/\gcd(A,B)\,.\, $ So you seek the first multiple of $\,m\,$ that is larger than $\,C,\,$  computable simply by an obvious division.
Note how use of $\,\rm lcm\,$ has allowed us to convert a problem from one with multiple divisibility relations to one involving  a single divisibility relation $\ A,\,B\ \mid  M\ \iff\ {\rm lcm}(A,B)\ |\ M.\,$ This, the universal definition of $\,{\rm lcm}\,$ is what allows us to reduce complex divisibility problems to single divisions - as occurs here, after we adjoin the additional constraint that $\, M > C\,,\,$ namely
$$\  A\,,B\ |\ M > C\ \ \iff\ \ {\rm lcm}(A,B)\ |\ M > C$$
For a universal proof of $\ \gcd(a,b)\,{\rm lcm}(a,b) = a\ b\ $ see  here or here.
A: Any common multiple of $A$ and $B$ is a multiple of the least common multiple, $\mathrm{lcm}(A,B)$.
The least common multiple can be found using the identity
$$\mathrm{lcm}(A,B)\gcd(A,B) = |AB|.$$
The $\gcd$ can be found using the Euclidean Algorithm, which does not require you to find the prime factorization. So you can find the least common multiple without knowing the prime factorization.
Once you know the lcm, call it $K$, then you are merely looking for the smallest integer $n$ such that $nK\gt C$. This is $n = \lceil \frac{C}{K}\rceil$ if $K\neq 0$. (And of course, if $K=0$, then that means that at least one of $A$ and $B$ is equal to $0$, and there is no solution).
In summary:


*

*Find the greatest common divisor (e.g., using the Euclidean algorithm);

*Compute $M=|AB|/\gcd(A,B)$.

*Find the smallest integer $k$ greater than or equal to $C/M$.

*The multiple you want is $kM$. 

