1
$\begingroup$

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)?

$\endgroup$
2
  • 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

0

Reset to default

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.