Given multiple ranges [L, R] and a prime number p, we need to find all P-smooth numbers in given individual ranges.
What is P – smooth number? An integer is P – smooth number if the largest Prime factor of that number <= p. 1 is considered (by OEIS) as P – smooth number for any possible value of P because it does not have any prime factor.
Examples:
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.
Suppose, we are checking 7 – smooth numbers. 1. Consider an integer 56. Here, 56 = 2 * 2 * 2 * 7. So, 56 has two prime factors (2 and 7) which are <=7. So, 56 is 7-smooth number. 2. Consider another integer 66. Here, 66 = 2 * 3 * 11. 66 has three prime factors (2, 3 and 11). Where 11>7. So 66 is not 7-smooth number. Brute – Force Approach: Let P and range [L, R] is given. Here L <= R. Create a loop and check for all numbers in inclusive range [L : R]. If that number has largest prime factor <= p. Then print that number (i.e. P-smooth number). Calculate its Largest Prime Factor / Divisor, using maxPrimeDivisor(n) function.
Efficient Approach: The idea is to pre-compute p-smooth numbers for maximum value of all ranges. Once we have pre-computed, we can quickly print for all ranges one by one.
C++
// C++ program to display p-smooth// number in given range.// P-smooth numbers' array#include <bits/stdc++.h>using namespace std;vector<int> p_smooth;// Returns Maximum Prime// Divisor of nint maxPrimeDivisor(int n){ int MPD = -1; if (n == 1) { return 1; } while (n % 2 == 0) { MPD = 2; n = n / 2; } // math.sqrt(n) + 1 int size = pow(n, 0.5) + 1; for (int odd = 3; odd < size; odd += 2) { while (n % odd == 0) { // Make sure no multiples // of prime, enters here MPD = odd; n /= odd; } } // When n is prime itself MPD = max(n, MPD); return MPD;}// generates p-smooth numbers.void generate_p_smooth(int p, int MAX_LIMIT){ for (int i = 2; i < MAX_LIMIT + 1; i++) { if (maxPrimeDivisor(i) <= p) { // Satisfies the condition // of p-smooth number p_smooth.push_back(i); } }}// finds p-smooth number in the// given [L:R] range.void find_p_smooth(int L, int R){ if (L <= p_smooth[p_smooth.size() - 1]) { // If user input exceeds MAX_LIMIT // range, no checking for (int i = 0; i < p_smooth.size(); i++) { int w = p_smooth[i]; if (w > R) break; if (w >= L && w <= R) { // Print P-smooth numbers // within range : L to R. cout << w << " "; } } cout << "\n"; }}// Driver Codeint main(){ p_smooth.push_back(1); // p_smooth number : p = 7 // L <= R int p = 7; int L = 1; int R = 100; // Maximum possible value of R int 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 phasing17 |
Java
// Java program to display p-smooth// number in given range.// P-smooth numbers' arrayimport java.util.*;class GFG { static ArrayList<Integer> p_smooth = new ArrayList<Integer>(); // Returns Maximum Prime // Divisor of n static int maxPrimeDivisor(int n) { int MPD = -1; if (n == 1) { return 1; } while (n % 2 == 0) { MPD = 2; n = n / 2; } // math.sqrt(n) + 1 int size = (int)Math.pow(n, 0.5) + 1; for (int odd = 3; odd < size; odd += 2) { while (n % odd == 0) { // Make sure no multiples // of prime, enters here MPD = odd; n /= odd; } } // When n is prime itself MPD = Math.max(n, MPD); return MPD; } // generates p-smooth numbers. static void generate_p_smooth(int p, int MAX_LIMIT) { for (int i = 2; i < MAX_LIMIT + 1; i++) { if (maxPrimeDivisor(i) <= p) { // Satisfies the condition // of p-smooth number p_smooth.add(i); } } } // finds p-smooth number in the // given [L:R] range. static void find_p_smooth(int L, int R) { if (L <= p_smooth.get(p_smooth.size() - 1)) { // If user input exceeds MAX_LIMIT // range, no checking for (int i = 0; i < p_smooth.size(); i++) { int w = p_smooth.get(i); if (w > R) break; if (w >= L && w <= R) { // Print P-smooth numbers // within range : L to R. System.out.print(w + " "); } } System.out.print("\n"); } } // Driver Code public static void main(String[] args) { p_smooth.add(1); // p_smooth number : p = 7 // L <= R int p = 7; int L = 1; int R = 100; // Maximum possible value of R int 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 phasing17 |
Python3
# Python program to display p-smooth# number in given range.# P-smooth numbers' arrayp_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 <= Rp = 7L, R = 1, 100 # Maximum possible value of RMAX_LIMIT = 1000 # generate the p-smooth numbersgenerate_p_smooth(p, MAX_LIMIT) # Find an print the p-smooth numbersfind_p_smooth(L, R) |
C#
// C# program to display p-smooth// number in given range.// P-smooth numbers' arrayusing System;using System.Collections.Generic;class GFG { static List<int> p_smooth = new List<int>(); // Returns Maximum Prime // Divisor of n static int maxPrimeDivisor(int n) { int MPD = -1; if (n == 1) { return 1; } while (n % 2 == 0) { MPD = 2; n = n / 2; } // math.sqrt(n) + 1 int size = (int)Math.Pow(n, 0.5) + 1; for (int odd = 3; odd < size; odd += 2) { while (n % odd == 0) { // Make sure no multiples // of prime, enters here MPD = odd; n /= odd; } } // When n is prime itself MPD = Math.Max(n, MPD); return MPD; } // generates p-smooth numbers. static void generate_p_smooth(int p, int MAX_LIMIT) { for (int i = 2; i < MAX_LIMIT + 1; i++) { if (maxPrimeDivisor(i) <= p) { // Satisfies the condition // of p-smooth number p_smooth.Add(i); } } } // finds p-smooth number in the // given [L:R] range. static void find_p_smooth(int L, int R) { if (L <= p_smooth[p_smooth.Count - 1]) { // If user input exceeds MAX_LIMIT // range, no checking for (int i = 0; i < p_smooth.Count; i++) { int w = p_smooth[i]; if (w > R) break; if (w >= L && w <= R) { // Print P-smooth numbers // within range : L to R. Console.Write(w + " "); } } Console.Write("\n"); } } // Driver Code public static void Main(string[] args) { p_smooth.Add(1); // p_smooth number : p = 7 // L <= R int p = 7; int L = 1; int R = 100; // Maximum possible value of R int 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 phasing17 |
Javascript
// JavaScript program to display p-smooth// number in given range.// P-smooth numbers' arraylet p_smooth = [1];// Returns Maximum Prime// Divisor of nfunction 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 <= Rlet p = 7;let L = 1;let R = 100;// Maximum possible value of Rlet MAX_LIMIT = 1000// generate the p-smooth numbersgenerate_p_smooth(p, MAX_LIMIT)// Find an print the p-smooth numbersfind_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
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
