Numbers with exactly 3 divisors using constant space
Run a loop from 2 to sqrt(N) and check if the current element is prime or not, if it is so then print that number, but this method will increase the time complexity of the solution
Follow the below steps to solve the problem:
- Start a loop for integer i from 2 to N.
- Check if i is prime or not, which can be done easily using the isPrime(n) method.
- If i is prime, check if its square is less than or equal to the given number. This will be reviewed only for squares of prime numbers, therefore reducing the number of checks.
- If the above condition is satisfied, the number will be printed and the loop will continue till i <= n.
Below is the implementation of the above approach:
// C++ program to print all
// three-primes smaller than
// or equal to n without using
// extra space
#include <bits/stdc++.h>
using namespace std;
void numbersWith3Divisors(int);
bool isPrime(int);
// Generates all primes upto n and
// prints their squares
void numbersWith3Divisors(int N)
{
cout << "Numbers with 3 divisors : " << endl;
for (int i = 2; i * i <= N; i++) {
// Check prime
if (isPrime(i)) {
// Print numbers in
// the order of
// occurrence
cout << i * i << " ";
}
}
}
// Check if a number is prime or not
bool isPrime(int N)
{
for (int i = 2; i * i <= N; i++) {
if (N % i == 0)
return false;
}
return true;
}
// Driver code
int main()
{
int N = 122;
// Function call
numbersWith3Divisors(N);
return 0;
}
// This code is contributed by vishu2908
// Java program to print all
// three-primes smaller than
// or equal to N without using
// extra space
import java.util.*;
class GFG {
// 3 divisor logic implementation
// check if a number is
// prime or not
// if it is a prime then
// check if its square
// is less than or equal to
// the given number
static void numbersWith3Divisors(int N)
{
System.out.println("Numbers with 3 divisors : ");
for (int i = 2; i * i <= N; i++) {
// Check prime
if (isPrime(i)) {
// Print numbers in
// the order of
// occurrence
System.out.print(i * i + " ");
}
}
}
// Check if a number is prime or not
public static boolean isPrime(int N)
{
for (int i = 2; i * i <= N; i++) {
if (N % i == 0)
return false;
}
return true;
}
// Driver code
public static void main(String[] args)
{
int N = 122;
// Function call
numbersWith3Divisors(N);
}
}
// Contributed by Parag Pallav Singh
# Python3 program to print all
# three-primes smaller than
# or equal to N without using
# extra space
# 3 divisor logic implementation
# check if a number is prime or
# not if it is a prime then check
# if its square is less than or
# equal to the given number
def numbersWith3Divisors(N):
print("Numbers with 3 divisors : ")
i = 2
while i * i <= N:
# Check prime
if (isPrime(i)):
# Print numbers in the order
# of occurrence
print(i * i, end=" ")
i += 1
# Check if a number is prime or not
def isPrime(N):
i = 2
while i * i <= N:
if N % i == 0:
return False
i += 1
return True
# Driver code
if __name__ == "__main__":
N = 122
# Function call
numbersWith3Divisors(N)
# This code is contributed by divyesh072019
// C# program to print all
// three-primes smaller than
// or equal to N without using
// extra space
using System;
class GFG {
// 3 divisor logic implementation
// check if a number is prime or
// not if it is a prime then check
// if its square is less than or
// equal to the given number
static void numbersWith3Divisors(int N)
{
Console.WriteLine("Numbers with 3 divisors : ");
for (int i = 2; i * i <= N; i++) {
// Check prime
if (isPrime(i)) {
// Print numbers in the order
// of occurrence
Console.Write(i * i + " ");
}
}
}
// Check if a number is prime or not
public static bool isPrime(int N)
{
for (int i = 2; i * i <= N; i++) {
if (N % i == 0)
return false;
}
return true;
}
// Driver code
static void Main()
{
int N = 122;
// Function call
numbersWith3Divisors(N);
}
}
// This code is contributed by divyeshrabadiya07
// Javascript program to print all
// three-primes smaller than
// or equal to n without using
// extra space
// 3 divisor logic implementation
// check if a number is prime or
// not if it is a prime then check
// if its square is less than or
// equal to the given number
function numbersWith3Divisors(n)
{
document.write("Numbers with 3 divisors : ");
for(let i = 2; i * i <= n; i++)
{
// Check prime
if (isPrime(i))
{
// Print numbers in the order
// of occurrence
document.write(i * i + " ");
}
}
}
// Check if a number is prime or not
function isPrime(n)
{
if (n == 0 || n == 1)
return false;
for(let i = 2; i * i <= n; i++)
{
if (n % i == 0)
return false;
}
return true;
}
let n = 122;
numbersWith3Divisors(n);
// This code is contributed by suresh07.
Output
Numbers with 3 divisors : 4 9 25 49 121
Time Complexity: O(sqrt N2)
Auxiliary Space: O(1)
Find numbers from 1 to N with exactly 3 divisors
Given a number N, print all numbers in the range from 1 to N having exactly 3 divisors.
Examples:
Input: N = 16
Output: 4 9
Explanation: 4 and 9 have exactly three divisors.Input: N = 49
Output: 4 9 25 49
Explanation: 4, 9, 25 and 49 have exactly three divisors.
Contact Us