Mathematical approach to find Numbers with exactly 3 divisors
To solve the problem follow the below idea:
Idea: After having a close look at the examples mentioned above, you have noticed that all the required numbers are perfect squares and that too of only prime numbers.
Proof: Suppose the number is N, and it is a perfect square with square root X such that X is prime.
Now if we find the factors of N, it will always have following combinations:
- 1*N
- X*X
Therefore the required numbers will have only three numbers as their divisors:
- 1,
- that number itself, and
- just a single divisor in between 1 and the number.
Algorithm: We can generate all primes within a set using any sieve method efficiently and then we should take all primes i, such that i*i <=N.
Follow the below steps to solve the problem:
- Generate the prime numbers from 1 to N using any sieve method efficiently
- Print all the prime numbers(X) between 1 to N, such as X2 is less than or equal to N
Below is the implementation of the above approach:
// C++ program to print all
// three-primes smaller than
// or equal to N using Sieve
// of Eratosthenes
#include <bits/stdc++.h>
using namespace std;
// Generates all primes upto N and
// prints their squares
void numbersWith3Divisors(int N)
{
bool prime[N + 1];
memset(prime, true, sizeof(prime));
prime[0] = prime[1] = 0;
for (int p = 2; p * p <= N; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= N; i += p)
prime[i] = false;
}
}
// Print squares of primes upto n.
cout << "Numbers with 3 divisors :\n";
for (int i = 0; i * i <= N; i++)
if (prime[i])
cout << i * i << " ";
}
// Driver code
int main()
{
int N = 96;
// Function call
numbersWith3Divisors(N);
return 0;
}
// Java program to print all
// three-primes smaller than
// or equal to N using Sieve
// of Eratosthenes
import java.io.*;
import java.util.*;
class GFG {
// Generates all primes upto N
// and prints their squares
static void numbersWith3Divisors(int N)
{
boolean[] prime = new boolean[N + 1];
Arrays.fill(prime, true);
prime[0] = prime[1] = false;
for (int p = 2; p * p <= N; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * 2; i <= N; i += p)
prime[i] = false;
}
}
// print squares of primes upto n
System.out.println("Numbers with 3 divisors : ");
for (int i = 0; i * i <= N; i++)
if (prime[i])
System.out.print(i * i + " ");
}
// Driver code
public static void main(String[] args)
{
int N = 96;
// Function call
numbersWith3Divisors(N);
}
}
// Contributed by Pramod Kumar
# Python3 program to print
# all three-primes smaller than
# or equal to n using Sieve
# of Eratosthenes
# Generates all primes upto n
# and prints their squares
def numbersWith3Divisors(N):
prime = [True]*(N+1)
prime[0] = prime[1] = False
p = 2
while (p*p <= N):
# If prime[p] is not changed,
# then it is a prime
if (prime[p] == True):
# Update all multiples of p
for i in range(p*2, N+1, p):
prime[i] = False
p += 1
# print squares of primes upto n.
print("Numbers with 3 divisors :")
i = 0
while (i*i <= N):
if (prime[i]):
print(i*i, end=" ")
i += 1
# Driver code
if __name__ == "__main__":
N = 96
# Function call
numbersWith3Divisors(N)
# This code is contributed by mits
// C# program to print all
// three-primes smaller than
// or equal to n using Sieve
// of Eratosthenes
class GFG {
// Generates all primes upto n
// and prints their squares
static void numbersWith3Divisors(int N)
{
bool[] prime = new bool[N + 1];
prime[0] = prime[1] = true;
for (int p = 2; p * p <= N; p++) {
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == false) {
// Update all multiples of p
for (int i = p * 2; i <= N; i += p)
prime[i] = true;
}
}
// print squares of primes upto n
System.Console.WriteLine(
"Numbers with 3 divisors : ");
for (int i = 0; i * i <= N; i++)
if (!prime[i])
System.Console.Write(i * i + " ");
}
// Driver code
public static void Main()
{
int N = 96;
// Function call
numbersWith3Divisors(N);
}
}
// This code is Contributed by mits
// Javascript program to print all
// three-primes smaller than
// or equal to n using Sieve
// of Eratosthenes
// Generates all primes upto n and
// prints their squares
function numbersWith3Divisors(n)
{
let prime = new Array(n+1);
prime.fill(true);
prime[0] = prime[1] = 0;
for (let p = 2; p*p <= n; p++)
{
// If prime[p] is not changed,
// then it is a prime
if (prime[p] == true)
{
// Update all multiples of p
for (let i = p*2; i <= n; i += p)
prime[i] = false;
}
}
// print squares of primes upto n.
document.write("Numbers with 3 divisors :" + "</br>");
for (let i = 0; i*i <= n ; i++)
if (prime[i])
document.write(i*i + " ");
}
// sieve();
let n = 96;
numbersWith3Divisors(n);
// This code is contributed by mukesh07.
<?php
// PHP program to print all three-primes
// smaller than or equal to n using Sieve
// of Eratosthenes
// Generates all primes upto n and
// prints their squares
function numbersWith3Divisors($N)
{
$prime = array_fill(0, $N + 1, true);
$prime[0] = $prime[1] = false;
for ($p = 2; $p * $p <= $N; $p++)
{
// If prime[p] is not changed,
// then it is a prime
if ($prime[$p] == true)
{
// Update all multiples of p
for ($i = $p * 2; $i <= $N; $i += $p)
$prime[$i] = false;
}
}
// print squares of primes upto n.
echo "Numbers with 3 divisors :\n";
for ($i = 0; $i * $i <= $N ; $i++)
if ($prime[$i])
echo $i * $i . " ";
}
// Driver Code
$N = 96;
// Function call
numbersWith3Divisors($N);
// This code is contributed by mits
?>
Output
Numbers with 3 divisors : 4 9 25 49
Time Complexity: O(N*log(log(N)))
Auxiliary Space: O(N)
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