Given a number 
. The task is to find all such numbers less than N and are a product of exactly two distinct prime numbers.
For Example, 33 is the product of two distinct primes i.e 11 * 3, whereas numbers like 60 which has three distinct prime factors i.e 2 * 2 * 3 * 5.
Note: These numbers cannot be a perfect square.
Examples:
Input : N = 30
Output : 6, 10, 14, 15, 21, 22, 26
Input : N = 50
Output : 6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46
Algorithm:
- Traverse till N and check whether each number has exactly two prime factors or not.
- Now to avoid the situation like 49 having 7 * 7 product of two prime numbers, check whether the number is a perfect square or not to ensure that it has two distinct prime.
- If Step 1 and Step 2 satisfies then add the number in the vector list.
- Traverse the vector and print all the elements in it.
Below is the implementation of the above approach:
C++
// C++ program to find numbers that are product// of exactly two distinct prime numbers#include <bits/stdc++.h>using namespace std;// Function to check whether a number// is a PerfectSquare or notbool isPerfectSquare(long double x){ long double sr = sqrt(x); return ((sr - floor(sr)) == 0);}// Function to check if a number is a// product of exactly two distinct primesbool isProduct(int num){ int cnt = 0; for (int i = 2; cnt < 2 && i * i <= num; ++i) { while (num % i == 0) { num /= i; ++cnt; } } if (num > 1) ++cnt; return cnt == 2;}// Function to find numbers that are product// of exactly two distinct prime numbers.void findNumbers(int N){ // Vector to store such numbers vector<int> vec; for (int i = 1; i <= N; i++) { if (isProduct(i) && !isPerfectSquare(i)) { // insert in the vector vec.push_back(i); } } // Print all numbers till n from the vector for (int i = 0; i < vec.size(); i++) { cout << vec[i] << " "; }}// Driver functionint main(){ int N = 30; findNumbers(N); return 0;} |
Java
// Java program to find numbers that are product// of exactly two distinct prime numbersimport java.util.*; class GFG{// Function to check whether a number// is a PerfectSquare or notstatic boolean isPerfectSquare(double x){ double sr = Math.sqrt(x); return ((sr - Math.floor(sr)) == 0);}// Function to check if a number is a// product of exactly two distinct primesstatic boolean isProduct(int num){ int cnt = 0; for (int i = 2; cnt < 2 && i * i <= num; ++i) { while (num % i == 0) { num /= i; ++cnt; } } if (num > 1) ++cnt; return cnt == 2;}// Function to find numbers that are product// of exactly two distinct prime numbers.static void findNumbers(int N){ // Vector to store such numbers Vector<Integer> vec = new Vector<Integer>(); for (int i = 1; i <= N; i++) { if (isProduct(i) && !isPerfectSquare(i)) { // insert in the vector vec.add(i); } } // Print all numbers till n from the vector Iterator<Integer> itr = vec.iterator(); while(itr.hasNext()){ System.out.print(itr.next()+" "); } }// Driver functionpublic static void main(String[] args){ int N = 30; findNumbers(N);}}// This Code is Contributed by mits |
Python 3
# Python 3 program to find numbers that are product# of exactly two distinct prime numbersimport math # Function to check whether a number# is a PerfectSquare or notdef isPerfectSquare(x): sr = math.sqrt(x) return ((sr - math.floor(sr)) == 0)# Function to check if a number is a# product of exactly two distinct primesdef isProduct( num): cnt = 0 i = 2 while cnt < 2 and i * i <= num: while (num % i == 0) : num //= i cnt += 1 i += 1 if (num > 1): cnt += 1 return cnt == 2 # Function to find numbers that are product# of exactly two distinct prime numbers.def findNumbers(N): # Vector to store such numbers vec = [] for i in range(1,N+1) : if (isProduct(i) and not isPerfectSquare(i)) : # insert in the vector vec.append(i) # Print all numbers till n from the vector for i in range(len( vec)): print(vec[i] ,end= " ") # Driver functionif __name__=="__main__": N = 30 findNumbers(N) |
C#
// C# program to find numbers that are product // of exactly two distinct prime numbers using System;using System.Collections.Generic;class GFG{ // Function to check whether a number // is a PerfectSquare or not static bool isPerfectSquare(double x) { double sr = Math.Sqrt(x); return ((sr - Math.Floor(sr)) == 0); } // Function to check if a number is a // product of exactly two distinct primes static bool isProduct(int num) { int cnt = 0; for (int i = 2; cnt < 2 && i * i <= num; ++i) { while (num % i == 0) { num /= i; ++cnt; } } if (num > 1) ++cnt; return cnt == 2; } // Function to find numbers that are product // of exactly two distinct prime numbers. static void findNumbers(int N) { // Vector to store such numbers List<int> vec = new List<int>(); for (int i = 1; i <= N; i++) { if (isProduct(i) && !isPerfectSquare(i)) { // insert in the vector vec.Add(i); } } // Print all numbers till n from the vector foreach(var a in vec) Console.Write(a + " "); } // Driver code public static void Main(String[] args) { int N = 30; findNumbers(N); } } // This code has been contributed by 29AjayKumar |
PHP
<?php// PHP program to find numbers that are product// of exactly two distinct prime numbers// Function to check whether a number// is a PerfectSquare or notfunction isPerfectSquare($x){ $sr = sqrt($x); return (($sr - floor($sr)) == 0);}// Function to check if a number is a// product of exactly two distinct primesfunction isProduct($num){ $cnt = 0; for ($i = 2; $cnt < 2 && $i * $i <= $num; ++$i) { while ($num % $i == 0) { $num /= $i; ++$cnt; } } if ($num > 1) ++$cnt; return $cnt == 2;}// Function to find numbers that are product// of exactly two distinct prime numbers.function findNumbers($N){ // Vector to store such numbers $vec = array(); for ($i = 1; $i <= $N; $i++) { if (isProduct($i) && !isPerfectSquare($i)) { // insert in the vector array_push($vec, $i); } } // Print all numbers till n from the vector for ($i = 0; $i < sizeof($vec); $i++) { echo $vec[$i] . " "; }}// Driver Code$N = 30;findNumbers($N);// This code is contributed by ita_c |
Javascript
<script>// Javascript program to find numbers that are product // of exactly two distinct prime numbers // Function to check whether a number // is a PerfectSquare or not function isPerfectSquare(x) { sr = Math.sqrt(x); return ((sr - Math.floor(sr)) == 0); } // Function to check if a number is a // product of exactly two distinct primes function isProduct(num) { var cnt = 0; for(var i = 2; cnt < 2 && (i * i) <= num; ++i) { while (num % i == 0) { num = parseInt(num / i); ++cnt; } } if (num > 1) ++cnt; return cnt == 2; } // Function to find numbers that are product // of exactly two distinct prime numbers. function findNumbers( N) { // Vector to store such numbers vec = []; for (var i = 1; i <= N; i++) { if (isProduct(i) && !isPerfectSquare(i)) { // insert in the vector vec.push(i); } } // Print all numbers till n from the vector for (var i = 0; i < vec.length; i++) { document.write(vec[i] + " "); } } // Driver function var N = 30; findNumbers(N);// This code is contributed by noob2000.</script> |
Output:
6 10 14 15 21 22 26
Time Complexity: O(
*
)
Auxiliary Space: O(n) , since n extra space has been taken.
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!
