A number is defined as being $B-Smooth$ if none of its prime factors are greater than the value of $B$. For example, $105$ is $7-Smooth$, because $105=3\cdot5\cdot7$.

Given a number $B$, how could you generate all $B-Smooth$ numbers up to a given number $N$?

Would it be best to check every number below $N$ to see if it is $B-Smooth$ by factorizing it? Would it be more efficient to generate all $B-Smooth$ numbers using a combination of powers on the products of all the primes up to $B$? Could you use a sieve method and simply remove numbers that are multiples of any prime greater than $B$ (like the sieve of Eratosthenes)?

  • 2
    $\begingroup$ I think a sieve is faster $\endgroup$
    – Peter
    Oct 5, 2020 at 18:10
  • 1
    $\begingroup$ If the number of prime factors is very small we only need to determine the limits for the corresponding exponents and can then very efficiently enumerate the numbers. $\endgroup$
    – Peter
    Oct 5, 2020 at 18:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.