P – números suaves en rangos dados

Dados múltiples rangos [L, R] y un número primo p, necesitamos encontrar todos los números P-lisos en rangos individuales dados.

¿Qué es P – número suave? Un número entero es P – número suave si el factor primo más grande de ese número <= p. 1 es considerado (por OEIS ) como P – número suave para cualquier valor posible de P porque no tiene ningún factor primo.

Ejemplos:

Input : p = 7   
        ranges[] = {[1, 17],  [10, 25]}

Output : 
For first range : 1 2 3 4 5 6 7 8 9 12 14 15 16
For second range : 15 16 18 20 21 24 25
Explanation : Largest prime factors of numbers
printed above are less than or equal to 7.

Supongamos que estamos comprobando 7: números suaves. 1. Considere un número entero 56. Aquí, 56 = 2 * 2 * 2 * 7. Entonces, 56 tiene dos factores primos (2 y 7) que son <=7. Entonces, 56 es 7-número liso. 2. Considere otro número entero 66. Aquí, 66 = 2 * 3 * 11. 66 tiene tres factores primos (2, 3 y 11). Donde 11>7. Así que 66 no es un número 7 suave. Enfoque de fuerza bruta: Sea P y se da el rango [L, R]. Aquí L <= R. Cree un ciclo y verifique todos los números en el rango inclusivo [L : R]. Si ese número tiene el factor primo más grande <= p. Luego imprima ese número (es decir, número P-suave). Calcule su mayor factor primo/divisor, utilizando la función maxPrimeDivisor(n) . 
Enfoque eficiente:La idea es precalcular números p-suaves para el valor máximo de todos los rangos. Una vez que hayamos calculado previamente, podemos imprimir rápidamente para todos los rangos uno por uno. 

# Python program to display p-smooth
# number in given range.
# P-smooth numbers' array
p_smooth = [1]
 
def maxPrimeDivisor(n):
     
    # Returns Maximum Prime
    # Divisor of n
    MPD = -1
     
    if n == 1 :
        return 1
     
    while n % 2 == 0:
        MPD = 2
        n = n // 2
     
    # math.sqrt(n) + 1
    size = int(n ** 0.5) + 1
    for odd in range( 3, size, 2 ):
        while n % odd == 0:
             
            # Make sure no multiples
            # of prime, enters here
            MPD = odd
            n = n // odd
     
    # When n is prime itself
    MPD = max (n, MPD)
     
    return MPD
 
 
def generate_p_smooth(p, MAX_LIMIT):   
     
    # generates p-smooth numbers.
    global p_smooth
     
    for i in range(2, MAX_LIMIT + 1):
        if maxPrimeDivisor(i) <= p:
             
            # Satisfies the condition
            # of p-smooth number
            p_smooth.append(i)
 
 
def find_p_smooth(L, R):
     
    # finds p-smooth number in the
    # given [L:R] range.
    global p_smooth
    if L <= p_smooth[-1]:
         
        # If user input exceeds MAX_LIMIT
        # range, no checking
        for w in p_smooth :
            if w > R : break
            if w >= L and w <= R :
                 
                # Print P-smooth numbers
                # within range : L to R.
                print(w, end =" ")
                 
        print()
         
# p_smooth number : p = 7
# L <= R
p = 7
L, R = 1, 100
 
# Maximum possible value of R
MAX_LIMIT = 1000
 
# generate the p-smooth numbers
generate_p_smooth(p, MAX_LIMIT)
 
# Find an print the p-smooth numbers
find_p_smooth(L, R)

// JavaScript program to display p-smooth
// number in given range.
// P-smooth numbers' array
let p_smooth = [1];
 
// Returns Maximum Prime
//  Divisor of n
function maxPrimeDivisor(n){
     
    let MPD = -1;
     
    if (n == 1){
        return 1;
    }
             
    while(n % 2 == 0){
        MPD = 2;
        n = Math.floor(n/2);       
    }
 
     
    // math.sqrt(n) + 1
    let size = Math.floor(n ** 0.5) + 1;
    for(let odd = 3; odd < size; odd += 2){
        while(n % odd == 0){       
            // Make sure no multiples
            // of prime, enters here
            MPD = odd;
            n = Math.floor(n/odd);             
        }
     
    }
 
    // When n is prime itself
    MPD = Math.max(n, MPD);
     
    return MPD;
}
 
 
// generates p-smooth numbers.
function generate_p_smooth(p, MAX_LIMIT){
 
    for(let i = 2; i < MAX_LIMIT+1; i++){
        if(maxPrimeDivisor(i) <= p){
            //Satisfies the condition
            // of p-smooth number
            p_smooth.push(i);              
        } 
    }
}
     
 
// finds p-smooth number in the
// given [L:R] range.
function find_p_smooth(L, R){
    if(L <= p_smooth[p_smooth.length-1]){       
        // If user input exceeds MAX_LIMIT
        // range, no checking
        for(let i = 0; i < p_smooth.length; i++){
            let w = p_smooth[i];
            if (w > R) break;
            if (w >= L && w <= R){           
                // Print P-smooth numbers
                // within range : L to R.
                document.write(w + " ");              
            }
 
        }
        document.write("\n");
    }
}
     
 
         
// p_smooth number : p = 7
// L <= R
let p = 7;
let L = 1;
let R = 100;
 
// Maximum possible value of R
let MAX_LIMIT = 1000
 
// generate the p-smooth numbers
generate_p_smooth(p, MAX_LIMIT)
 
// Find an print the p-smooth numbers
find_p_smooth(L, R)
 
// The code is contributed by Gautam goel (gautamgoel962)

Output: 
1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24 25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64 70 72 75 80 81 84 90 96 98 100