A P-smooth number or P-friable number is an integer whose largest prime factor is less than or equal to P. Given N and P, we need to write a program to check whether it is P-friable or not.
Examples:
Input : N = 24 , P = 7
Output : YES
Explanation : The prime divisors of 24 are 2 and 3 only.
Hence its largest prime factor is 3 which
is less than or equal to 7, it is P-friable.
Input : N = 22 , P = 5
Output : NO
Explanation : The prime divisors are 11 and 2, hence 11>5,
so it is not a P-friable number.
The approach will be to prime factorize the number and store the maximum of all the prime factors. We first divide the number by 2 if it is divisible, then we iterate from 3 to Sqrt(n) to get the number of times a prime number divides a particular number which reduces every time by n/i and store the prime factor i if its divides N. We divide our number n (by prime factors) by its corresponding smallest prime factor till n becomes 1. And if at the end n > 2, it means its a prime number, so we store that as a prime factor as well. At the end the largest factor is compared with p to check if it is p-smooth number or not.
C++
// CPP program to check if a number is// a p-smooth number or not#include <iostream>#include<math.h>using namespace std;// function to check if number n// is a P-smooth number or notbool check(int n, int p) { int maximum = -1; // prime factorise it by 2 while (!(n % 2)) { // if the number is divisible by 2 maximum = max(maximum, 2); n = n/2; } // check for all the possible numbers // that can divide it for (int i = 3; i <= sqrt(n); i += 2) { // prime factorize it by i while (n % i == 0) { // stores the maximum if maximum // and i, if i divides the number maximum = max(maximum,i); n = n / i; } } // if n at the end is a prime number, // then it a divisor itself if (n > 2) maximum = max(maximum, n); return (maximum <= p);}// Driver program to test above functionint main() { int n = 24, p = 7; if (check(n, p)) cout << "yes"; else cout << "no"; return 0;} |
Java
// Java program to check if a number is// a p-smooth number or notimport java.lang.*;class GFG{// function to check if number n// is a P-smooth number or notstatic boolean check(int n, int p) { int maximum = -1; // prime factorise it by 2 while ((n % 2) == 0) { // if the number is divisible by 2 maximum = Math.max(maximum, 2); n = n/2; } // check for all the possible numbers // that can divide it for (int i = 3; i <= Math.sqrt(n); i += 2) { // prime factorize it by i while (n % i == 0) { // stores the maximum if maximum // and i, if i divides the number maximum = Math.max(maximum,i); n = n / i; } } // if n at the end is a prime number, // then it a divisor itself if (n > 2) maximum = Math.max(maximum, n); return (maximum <= p);}// Driver program to test// above functionpublic static void main(String[] args) { int n = 24, p = 7; if (check(n, p)) System.out.println("yes"); else System.out.println("no"); }}// This code is contributed by// Smitha Dinesh Semwal |
Python3
# Python 3 program to# check if a number is# a p-smooth number or notimport math# function to check if number n# is a P-smooth number or notdef check(n, p) : maximum = -1 # prime factorise it by 2 while (not(n % 2)): # if the number is divisible by 2 maximum = max(maximum, 2) n = int(n/2) # check for all the possible numbers # that can divide it for i in range(3,int(math.sqrt(n)), 2): # prime factorize it by i while (n % i == 0) : # stores the maximum if maximum # and i, if i divides the number maximum = max(maximum,i) n = int(n / i) # if n at the end is a prime number, # then it a divisor itself if (n > 2): maximum = max(maximum, n) return (maximum <= p)# Driver program to test above functionn = 24p = 7if (check(n, p)): print( "yes" )else: print( "no" )# This code is contributed by# Smitha Dinesh Semwal |
C#
// C# program to check if a number is// a p-smooth number or notusing System;class GFG { // function to check if number n // is a P-smooth number or not static bool check(int n, int p) { int maximum = -1; // prime factorise it by 2 while ((n % 2) == 0) { // if the number is divisible by 2 maximum = Math.Max(maximum, 2); n = n / 2; } // check for all the possible numbers // that can divide it for (int i = 3; i <= Math.Sqrt(n); i += 2) { // prime factorize it by i while (n % i == 0) { // stores the maximum if maximum // and i, if i divides the number maximum = Math.Max(maximum, i); n = n / i; } } // if n at the end is a prime number, // then it a divisor itself if (n > 2) maximum = Math.Max(maximum, n); return (maximum <= p); } // Driver program to test // above function public static void Main() { int n = 24, p = 7; if (check(n, p)) Console.Write("yes"); else Console.Write("no"); }}// This code is contributed by vt_m. |
PHP
<?php// PHP program to check if a number is// a p-smooth number or not// function to check if number n// is a P-smooth number or notfunction check($n, $p) { $maximum = -1; // prime factorise it by 2 while (!($n % 2)) { // if the number is // divisible by 2 $maximum = max($maximum, 2); $n = $n / 2; } // check for all the possible // numbers that can divide it for ($i = 3; $i <= sqrt($n); $i += 2) { // prime factorize it by i while ($n % $i == 0) { // stores the maximum if maximum // and i, if i divides the number $maximum = max($maximum, $i); $n = $n / $i; } } // if n at the end is a prime number, // then it a divisor itself if ($n > 2) $maximum = max($maximum, $n); return ($maximum <= $p);}// Driver Code$n = 24; $p = 7; if (check($n, $p)) echo("yes");else echo("no"); // This code is contributed by Ajit.?> |
Javascript
<script>// Javascript program to check if a number is// a p-smooth number or not // function to check if number n // is a P-smooth number or not function check(n, p) { let maximum = -1; // prime factorise it by 2 while (!(n % 2)) { // if the number is divisible by 2 maximum = Math.max(maximum, 2) n = n/2; } // check for all the possible numbers // that can divide it var i; for (i = 3; i*i <= n; i += 2) { // prime factorize it by i while (n % i == 0) { // stores the maximum if maximum // and i, if i divides the number maximum = Math.max(maximum, i); n = n / i; } } // if n at the end is a prime number, // then it a divisor itself if (n > 2) maximum = Math.max(maximum, n); if (maximum <= p) return true; else return false; } // Driver Code let n = 24, p = 7; if (check(n, p)) document.write("yes"); else document.write("no"); // This code is contributed by ajaykrsharma132.</script> |
Output:
yes
Time Complexity: O(sqrt(N)*logN), as we are using nested loops to traverse sqrt(N)*logN times.
Auxiliary Space: O(1), as we are not using any extra space.
Reference:
http://oeis.org/wiki/P-smooth_numbers
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!
