A k-rough or k-jagged number is a number whose smallest prime factor is greater than or equal to the number ‘k’. Given numbers ‘n’ and ‘k’ as input, we are required to find whether ‘n; is a k-rough number or not.
Examples :
Input : n = 10, k = 2
Output : 10 is a 2-rough number
Explanation: The prime factors of 10 are 2 and 5 Hence its smallest prime factor is 2 which is greater than or equal to k, i.e 2
Input : n = 55, k = 7
Output : 55 is not a 7-rough number
Explanation: The prime factors of 55 are 5 and 11 Hence its smallest prime factor is 5 which is not greater than or equal to k, i.e 7
It may be inferred from above that every positive integer, except 1, is a 2-rough number since their smallest prime factor is either 2(for even positive integers) or greater than 2(for odd positive integers).
Simple Approach
- First find all prime numbers up to the number ‘n’.
- Next find the smallest prime factor of the number ‘n’ from its prime factorization.
- Check if the smallest prime factor is greater than or equal to ‘k’ or not.
C++
// CPP to check if n is a k-rough number// or not#include <bits/stdc++.h>using namespace std;// Finds primes by Sieve of Eratosthenes// methodvector<int> getPrimes(int n){ int i, j; bool isPrime[n + 1]; memset(isPrime, true, sizeof(isPrime)); for (i = 2; i * i <= n; i++) { // If isPrime[i] is not changed, // then it is prime if (isPrime[i] == true) { // Update all multiples of p for (j = i * 2; j <= n; j += i) isPrime[j] = false; } } // Forming array of the prime numbers found vector<int> primes; for (i = 2; i <= n; i++) if (isPrime[i]) primes.push_back(i); return primes;}// Checking whether a number is k-rough or notbool isRough(int n, int k){ vector<int> primes = getPrimes(n); // Finding minimum prime factor of n int min_pf = n; for (int i = 0; i < primes.size(); i++) if (n % primes[i] == 0) min_pf = primes[i]; // Return true if minimum prime factor // is greater than or equal to k. Else // return false. return (min_pf >= k);}// Driver Methodint main(){ int n = 75, k = 3; if (isRough(n, k)) cout << n << " is a " << k << "-rough number\n"; else cout << n << " is not a " << k << "-rough number\n"; return 0;} |
Java
// Java to check if n is // a k-rough number or notimport java.io.*;import java.util.*;class GFG { // Finds primes by Sieve // of Eratosthenes method static ArrayList<Integer> getPrimes(int n) { int i, j; int []isPrime = new int[n + 1]; for(i = 0; i < n + 1; i++) isPrime[i] = 1; for (i = 2; i * i <= n; i++) { // If isPrime[i] is not // changed, then it is prime if (isPrime[i] == 1) { // Update all // multiples of p for (j = i * 2; j <= n; j += i) isPrime[j] = 0; } } // Forming array of the // prime numbers found ArrayList<Integer> primes = new ArrayList<Integer>(); for (i = 2; i <= n; i++) if (isPrime[i] == 1) primes.add(i); return primes; } // Checking whether a // number is k-rough or not static boolean isRough(int n, int k) { ArrayList<Integer> primes = getPrimes(n); // Finding minimum // prime factor of n int min_pf = n; for (int i = 0; i < primes.size(); i++) if (n % primes.get(i) == 0) min_pf = primes.get(i); // Return true if minimum // prime factor is greater // than or equal to k. Else // return false. return (min_pf >= k); } // Driver Code public static void main(String args[]) { int n = 75, k = 3; if (isRough(n, k)) System.out.print(n + " is a " + k + "-rough number\n"); else System.out.print(+ n + " is not a " + k + "-rough number\n"); }}// This code is contributed by // Manish Shaw.(manishshaw1) |
Python3
# Python3 to check if n is a k-rough# number or not# Finds primes by Sieve of Eratosthenes methoddef getPrimes(n): isPrime = [True] * (n + 1); i = 2; while (i * i <= n): # If isPrime[i] is not changed, # then it is prime if (isPrime[i] == True): # Update all multiples of p j = i * 2; while (j <= n): isPrime[j] = False; j += i; i += 1; # Forming array of the # prime numbers found primes = []; for i in range(2, n + 1): if (isPrime[i]): primes.append(i); return primes;# Checking whether a # number is k-rough or notdef isRough(n, k): primes = getPrimes(n); # Finding minimum # prime factor of n min_pf = n; for i in range(len(primes)): if (n % primes[i] == 0): min_pf = primes[i]; # Return true if minimum # prime factor is greater # than or equal to k. Else # return false. return (min_pf >= k);# Driver Coden = 75; k = 3;if (isRough(n, k)): print(n, "is a", k,"-rough number");else: print(n, "is not a", k, "-rough number"); # This code is contributed by mits |
C#
// C# to check if n is a k-rough number// or notusing System;using System.Collections.Generic;using System.Linq;class GFG { // Finds primes by Sieve of Eratosthenes // method static List<int> getPrimes(int n) { int i, j; int []isPrime = new int[n + 1]; for(i = 0; i < n + 1; i++) isPrime[i] = 1; // Array.Clear(isPrime, 1, isPrime.Length); for (i = 2; i * i <= n; i++) { // If isPrime[i] is not changed, // then it is prime if (isPrime[i] == 1) { // Update all multiples of p for (j = i * 2; j <= n; j += i) isPrime[j] = 0; } } // Forming array of the prime numbers // found List<int> primes = new List<int>(); for (i = 2; i <= n; i++) if (isPrime[i] == 1) primes.Add(i); return primes; } // Checking whether a number is k-rough // or not static bool isRough(int n, int k) { List<int> primes = getPrimes(n); // Finding minimum prime factor of n int min_pf = n; for (int i = 0; i < primes.Count; i++) if (n % primes[i] == 0) min_pf = primes[i]; // Return true if minimum prime factor // is greater than or equal to k. Else // return false. return (min_pf >= k); } // Driver Method static void Main() { int n = 75, k = 3; if (isRough(n, k)) Console.Write(n + " is a " + k + "-rough number\n"); else Console.Write(+ n + " is not a " + k + "-rough number\n"); }}// This code is contributed by manishshaw. |
PHP
<?php// PHP to check if n is // a k-rough number or not// Finds primes by Sieve // of Eratosthenes methodfunction getPrimes($n){ $isPrime = array_fill(0, ($n + 1), true); for ($i = 2; $i * $i <= $n; $i++) { // If isPrime[i] is // not changed, // then it is prime if ($isPrime[$i] == true) { // Update all // multiples of p for ($j = $i * 2; $j <= $n; $j += $i) $isPrime[$j] = false; } } // Forming array of the // prime numbers found $primes = array(); $k = 0; for ($i = 2; $i <= $n; $i++) if ($isPrime[$i]) $primes[$k++]=$i; return $primes;}// Checking whether a // number is k-rough or notfunction isRough($n, $k){ $primes = getPrimes($n); // Finding minimum // prime factor of n $min_pf = $n; for ($i = 0; $i < count($primes); $i++) if ($n % $primes[$i] == 0) $min_pf = $primes[$i]; // Return true if minimum // prime factor is greater // than or equal to k. Else // return false. return ($min_pf >= $k);}// Driver Code$n = 75; $k = 3;if (isRough($n, $k)) echo $n . " is a " . $k . "-rough number\n";else echo $n . " is not a " . $k . "-rough number\n"; // This code is contributed by mits?> |
Javascript
<script>// Javascript to check if n is a k-rough number// or not// Finds primes by Sieve of Eratosthenes// methodfunction getPrimes(n){ var i, j; var isPrime = Array(n+1).fill(true); for (i = 2; i * i <= n; i++) { // If isPrime[i] is not changed, // then it is prime if (isPrime[i] == true) { // Update all multiples of p for (j = i * 2; j <= n; j += i) isPrime[j] = false; } } // Forming array of the prime numbers found var primes = []; for (i = 2; i <= n; i++) if (isPrime[i]) primes.push(i); return primes;}// Checking whether a number is k-rough or notfunction isRough(n, k){ var primes = getPrimes(n); // Finding minimum prime factor of n var min_pf = n; for (var i = 0; i < primes.length; i++) if (n % primes[i] == 0) min_pf = primes[i]; // Return true if minimum prime factor // is greater than or equal to k. Else // return false. return (min_pf >= k);}// Driver Methodvar n = 75, k = 3;if (isRough(n, k)) document.write( n + " is a " + k + "-rough number<br>");else document.write( n + " is not a " + k + "-rough number<br>");// This code is contributed by itsok.</script> |
Output:
75 is a 3-rough number
Time Complexity: O(?n log n)
Auxiliary Space: O(n)
Efficient Solution :
The idea is based on Efficient program to print all prime factors of a given number.
- If n is divisible by 2 (smallest prime number), then we return true if k is smaller than or equal to 2. Else we return false.
- Then we one by one try all odd numbers. As soon as we find an odd number that divides n, we compare it with k and return true if the odd number is greater than or equal to k, else false. This solution works because if a prime number does not divide n, then its multiples will also not divide.
C++
// CPP program to check if given n is// k-rough or not.# include <bits/stdc++.h>using namespace std;// Returns true if n is k rough else falsebool isKRough(int n, int k){ // If n is even, then smallest prime // factor becomes 2. if (n % 2 == 0) return (k <= 2); // n must be odd at this point. So we // can skip one element (Note i = i +2) for (int i = 3; i*i <= n; i = i+2) if (n%i == 0) return (i >= k); return (n >= k);}/* Driver program to test above function */int main(){ int n = 75, k = 3; if (isKRough(n, k)) cout << n << " is a " << k << "-rough number\n"; else cout << n << " is not a " << k << "-rough number\n"; return 0;} |
Java
// Java program to check if given n is// k-rough or not.class GFG { // Returns true if n is k rough else falsestatic boolean isKRough(int n, int k){ // If n is even, then smallest // prime factor becomes 2. if (n % 2 == 0) return (k <= 2); // n must be odd at this point. So we // can skip one element (Note i = i + 2) for (int i = 3; i*i <= n; i = i + 2) if (n % i == 0) return (i >= k);return (n >= k);}/* Driver program to test above function */public static void main(String[] args){ int n = 75, k = 3; if (isKRough(n, k)) System.out.println(n + " is a " + k + "-rough number"); else System.out.println(n + " is not a " + k + "-rough number");}}// This code is contributed by Smitha |
Python3
# Python3 program to check if given n # is k-rough or not.# Returns true if n is k rough else falsedef isKRough(n, k): # If n is even, then smallest # prime factor becomes 2. if(n % 2 == 0): return (k <= 2); # n must be odd at this point. # So we can skip one element # (Note i = i +2) i = 3; while(i * i <= n): if(n % i == 0): return (i >= k); i = i + 2; return (n >= k);# Driver Coden = 75;k = 3;if (isKRough(n, k)): print(n, "is a", k, "-rough number");else: print(n, "is not a", k, "-rough number"); # This code is contributed by mits |
C#
// C# program to check if given n is// k-rough or not.using System;class GFG { // Returns true if n is k rough else falsestatic bool isKRough(int n, int k){ // If n is even, then smallest prime // factor becomes 2. if (n % 2 == 0) return (k <= 2); // n must be odd at this point. So we // can skip one element (Note i = i + 2) for (int i = 3; i*i <= n; i = i + 2) if (n % i == 0) return (i >= k);return (n >= k);}/* Driver program to test above function */public static void Main(){ int n = 75, k = 3; if (isKRough(n, k)) Console.Write(n + " is a " + k + "-rough number\n"); else Console.Write(n + " is not a " + k + "-rough number\n");}}// This code is contributed by Smitha |
PHP
<?php// PHP program to check if // given n is k-rough or not.// Returns true if n is k // rough else falsefunction isKRough($n, $k){ // If n is even, then smallest // prime factor becomes 2. if ($n % 2 == 0) return ($k <= 2); // n must be odd at this point. // So we can skip one element // (Note i = i +2) for ($i = 3; $i * $i <= $n; $i = $i + 2) if ($n % $i == 0) return ($i >= $k);return ($n >= $k);}// Driver Code$n = 75;$k = 3;if (isKRough($n, $k)) echo $n . " is a " . $k . "-rough number\n";else echo $n . " is not a " . $k . "-rough number\n"; // This code is contributed by Sam007?> |
Javascript
<script>// Javascript program to check if// given n is k-rough or not.// Returns true if n is k// rough else falsefunction isKRough(n, k){ // If n is even, then smallest // prime factor becomes 2. if (n % 2 == 0) return (k <= 2); // n must be odd at this point. // So we can skip one element // (Note i = i +2) for (let i = 3; i * i <= n; i = i + 2) if (n % i == 0) return (i >= k);return (n >= k);}// Driver Codelet n = 75;let k = 3;if (isKRough(n, k)) document.write( n + " is a " + k + "-rough number<br>");else document.write( n + " is not a " + k + "-rough number<br>"); // This code is contributed by sravan kumar</script> |
Output :
75 is a 3-rough number
Time Complexity: O(?n)
Auxiliary Space: O(1)
Please suggest if someone has a better solution which is more efficient in terms of space and time.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
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!
