Check if a number is an unusual number or not
In this article, we will discuss how to determine if a given number is an unusual number or not. An unusual number is defined as a number for which the largest prime factor is greater than the square root of the number. We will provide a program to check for unusual numbers and explain its logic step by step.
Problem Statement
We are given a positive integer number, and we need to check whether it is an unusual number or not. An unusual number is a number where the largest prime factor is greater than the square root of the number.
Example
Let's take a few examples to understand the concept of unusual numbers:
-
For the number 14: The prime factors of 14 are 2 and 7. The largest prime factor is 7, which is greater than the square root of 14 (approximately 3.74). Hence, 14 is an unusual number.
-
For the number 34: The prime factors of 34 are 2 and 17. The largest prime factor is 17, which is greater than the square root of 34 (approximately 5.83). Thus, 34 is also an unusual number.
-
For the number 50: The prime factors of 50 are 2 and 5. The largest prime factor is 5, which is not greater than the square root of 50 (approximately 7.07). Therefore, 50 is not an unusual number.
Pseudocode and Algorithm
Function largest_prime_factor(number):
result = -1
n = number
// Execute this loop until n is an odd number
while n % 2 == 0:
result = 2
n = n / 2
i = 3
sqrt_value = integer part of square root of n
// Loop to find prime factors starting from 3 up to sqrt_value
while i <= sqrt_value:
while n % i == 0:
result = i
n = n / i
i += 2
// If n is greater than 2, update the result to n
if n > 2:
result = n
return result
Function is_unusual_no(number):
factor = -1
if number > 0:
factor = largest_prime_factor(number)
// Check if the largest prime factor is greater than the square root of the number
if factor > -1 and factor > integer part of square root of number:
Print "[number] is unusual number"
else:
Print "[number] is not unusual number"
Main:
number = 14
Call is_unusual_no(number)
number = 34
Call is_unusual_no(number)
number = 50
Call is_unusual_no(number)
- Define a function
largest_prime_factor(number)
that takes an integer as input and returns the largest prime factor of that number. - Initialize a variable
result
to -1. This variable will store the largest prime factor. - Divide the input number
number
by 2 until it becomes an odd number, and at each step, update theresult
to 2 (since 2 is the smallest prime factor). This step ensures that the number becomes odd. - Calculate the square root of the updated number and store it in
sqrt_value
. - Starting from 3, iterate over all odd numbers up to
sqrt_value
. - For each odd number
i
, check if it is a factor of the updated number (number
). If it is a factor, update theresult
toi
and divide the number byi
. - Repeat step 6 until there are no more factors of
i
in the number. - If the remaining number (
n
) after the loop is greater than 2, update theresult
ton
. - Return the
result
.
Code Solution
Here given code implementation process.
// C Program
// Check if a number is an unusual number or not
#include <stdio.h>
#include <math.h>
int largest_prime_factor(int number)
{
int result = -1;
int n = number;
// Execute this loop until, when the n is a odd number
while (n % 2 == 0)
{
result = 2;
n = n / 2;
}
// Loop controlling variable
int i = 0;
int sqrt_value = (int) sqrt(n);
for (i = 3; i <= sqrt_value; i += 2)
{
while (n % i == 0)
{
// When [i] is factor of n
result = i;
n = n / i;
}
}
if (n > 2)
{
// When n is greater than 2
result = n;
}
return result;
}
// Determine whether given number is unusual number or not
void is_unusual_no(int number)
{
int factor = -1;
if (number > 0)
{
factor = largest_prime_factor(number);
}
if (factor > -1 && factor > sqrt(number))
{
printf("\n [%d] is unusual number", number);
}
else
{
printf("\n [%d] is not unusual number", number);
}
}
// Driver Code
int main()
{
int number = 14;
//Test case
is_unusual_no(number);
number = 34;
is_unusual_no(number);
number = 50;
is_unusual_no(number);
return 0;
}
Output
[14] is unusual number
[34] is unusual number
[50] is not unusual number
/*
Java program
Check if a number is an unusual number or not
*/
class UnusualNumber
{
public int largest_prime_factor(int number)
{
int result = -1;
int n = number;
// Execute this loop until, when the n is a odd number
while (n % 2 == 0)
{
result = 2;
n = n / 2;
}
// Loop controlling variable
int i = 0;
int sqrt_value = (int) Math.sqrt(n);
for (i = 3; i <= sqrt_value; i += 2)
{
while (n % i == 0)
{
// When [i] is factor of n
result = i;
n = n / i;
}
}
if (n > 2)
{
// When n is greater than 2
result = n;
}
return result;
}
// Determine whether given number is unusual number or not
public void is_unusual_no(int number)
{
int factor = -1;
if (number > 0)
{
factor = largest_prime_factor(number);
}
if (factor > -1 && factor > Math.sqrt(number))
{
System.out.print("\n [" + number + "] is unusual number");
}
else
{
System.out.print("\n [" + number + "] is not unusual number");
}
}
public static void main(String[] args)
{
UnusualNumber obj = new UnusualNumber();
int number = 14;
//Test case
obj.is_unusual_no(number);
number = 34;
obj.is_unusual_no(number);
number = 50;
obj.is_unusual_no(number);
}
}
Output
[14] is unusual number
[34] is unusual number
[50] is not unusual number
//Include header file
#include <iostream>
#include<math.h>
using namespace std;
/*
C++ program
Check if a number is an unusual number or not
*/
class UnusualNumber
{
public: int largest_prime_factor(int number)
{
int result = -1;
int n = number;
// Execute this loop until, when the n is a odd number
while (n % 2 == 0)
{
result = 2;
n = n / 2;
}
// Loop controlling variable
int i = 0;
int sqrt_value = (int) sqrt(n);
for (i = 3; i <= sqrt_value; i += 2)
{
while (n % i == 0)
{
// When [i] is factor of n
result = i;
n = n / i;
}
}
if (n > 2)
{
// When n is greater than 2
result = n;
}
return result;
}
// Determine whether given number is unusual number or not
void is_unusual_no(int number)
{
int factor = -1;
if (number > 0)
{
factor = this->largest_prime_factor(number);
}
if (factor > -1 && factor > sqrt(number))
{
cout << "\n [" << number << "] is unusual number";
}
else
{
cout << "\n [" << number << "] is not unusual number";
}
}
};
int main()
{
UnusualNumber obj = UnusualNumber();
int number = 14;
//Test case
obj.is_unusual_no(number);
number = 34;
obj.is_unusual_no(number);
number = 50;
obj.is_unusual_no(number);
return 0;
}
Output
[14] is unusual number
[34] is unusual number
[50] is not unusual number
//Include namespace system
using System;
/*
C# program
Check if a number is an unusual number or not
*/
class UnusualNumber
{
public int largest_prime_factor(int number)
{
int result = -1;
int n = number;
// Execute this loop until, when the n is a odd number
while (n % 2 == 0)
{
result = 2;
n = n / 2;
}
// Loop controlling variable
int i = 0;
int sqrt_value = (int) Math.Sqrt(n);
for (i = 3; i <= sqrt_value; i += 2)
{
while (n % i == 0)
{
// When [i] is factor of n
result = i;
n = n / i;
}
}
if (n > 2)
{
// When n is greater than 2
result = n;
}
return result;
}
// Determine whether given number is unusual number or not
public void is_unusual_no(int number)
{
int factor = -1;
if (number > 0)
{
factor = largest_prime_factor(number);
}
if (factor > -1 && factor > Math.Sqrt(number))
{
Console.Write("\n [" + number + "] is unusual number");
}
else
{
Console.Write("\n [" + number + "] is not unusual number");
}
}
public static void Main(String[] args)
{
UnusualNumber obj = new UnusualNumber();
int number = 14;
//Test case
obj.is_unusual_no(number);
number = 34;
obj.is_unusual_no(number);
number = 50;
obj.is_unusual_no(number);
}
}
Output
[14] is unusual number
[34] is unusual number
[50] is not unusual number
<?php
/*
Php program
Check if a number is an unusual number or not
*/
class UnusualNumber
{
public function largest_prime_factor($number)
{
$result = -1;
$n = $number;
// Execute this loop until, when the n is a odd number
while ($n % 2 == 0)
{
$result = 2;
$n = intval($n / 2);
}
// Loop controlling variable
$i = 0;
$sqrt_value = (int) sqrt($n);
for ($i = 3; $i <= $sqrt_value; $i += 2)
{
while ($n % $i == 0)
{
// When [i] is factor of n
$result = $i;
$n = intval($n / $i);
}
}
if ($n > 2)
{
// When n is greater than 2
$result = $n;
}
return $result;
}
// Determine whether given number is unusual number or not
public function is_unusual_no($number)
{
$factor = -1;
if ($number > 0)
{
$factor = $this->largest_prime_factor($number);
}
if ($factor > -1 && $factor > sqrt($number))
{
echo "\n [". $number ."] is unusual number";
}
else
{
echo "\n [". $number ."] is not unusual number";
}
}
}
function main()
{
$obj = new UnusualNumber();
$number = 14;
//Test case
$obj->is_unusual_no($number);
$number = 34;
$obj->is_unusual_no($number);
$number = 50;
$obj->is_unusual_no($number);
}
main();
Output
[14] is unusual number
[34] is unusual number
[50] is not unusual number
/*
Node Js program
Check if a number is an unusual number or not
*/
class UnusualNumber
{
largest_prime_factor(number)
{
var result = -1;
var n = number;
// Execute this loop until, when the n is a odd number
while (n % 2 == 0)
{
result = 2;
n = parseInt(n / 2);
}
// Loop controlling variable
var i = 0;
var sqrt_value = parseInt(Math.sqrt(n));
for (i = 3; i <= sqrt_value; i += 2)
{
while (n % i == 0)
{
// When [i] is factor of n
result = i;
n = parseInt(n / i);
}
}
if (n > 2)
{
// When n is greater than 2
result = n;
}
return result;
}
// Determine whether given number is unusual number or not
is_unusual_no(number)
{
var factor = -1;
if (number > 0)
{
factor = this.largest_prime_factor(number);
}
if (factor > -1 && factor > Math.sqrt(number))
{
process.stdout.write("\n [" + number + "] is unusual number");
}
else
{
process.stdout.write("\n [" + number + "] is not unusual number");
}
}
}
function main()
{
var obj = new UnusualNumber();
var number = 14;
//Test case
obj.is_unusual_no(number);
number = 34;
obj.is_unusual_no(number);
number = 50;
obj.is_unusual_no(number);
}
main();
Output
[14] is unusual number
[34] is unusual number
[50] is not unusual number
import math
# Python 3 program
# Check if a number is an unusual number or not
class UnusualNumber :
def largest_prime_factor(self, number) :
result = -1
n = number
# Execute this loop until, when the n is a odd number
while (n % 2 == 0) :
result = 2
n = int(n / 2)
sqrt_value = int(math.sqrt(n))
# Loop controlling variable
i = 3
while (i <= sqrt_value) :
while (n % i == 0) :
# When [i] is factor of n
result = i
n = int(n / i)
i += 2
if (n > 2) :
# When n is greater than 2
result = n
return result
# Determine whether given number is unusual number or not
def is_unusual_no(self, number) :
factor = -1
if (number > 0) :
factor = self.largest_prime_factor(number)
if (factor > -1 and factor > math.sqrt(number)) :
print("\n [", number ,"] is unusual number", end = "")
else :
print("\n [", number ,"] is not unusual number", end = "")
def main() :
obj = UnusualNumber()
number = 14
# Test case
obj.is_unusual_no(number)
number = 34
obj.is_unusual_no(number)
number = 50
obj.is_unusual_no(number)
if __name__ == "__main__": main()
Output
[ 14 ] is unusual number
[ 34 ] is unusual number
[ 50 ] is not unusual number
# Ruby program
# Check if a number is an unusual number or not
class UnusualNumber
def largest_prime_factor(number)
result = -1
n = number
# Execute this loop until, when the n is a odd number
while (n % 2 == 0)
result = 2
n = n / 2
end
sqrt_value = (Math.sqrt(n)).to_i
# Loop controlling variable
i = 3
while (i <= sqrt_value)
while (n % i == 0)
# When [i] is factor of n
result = i
n = n / i
end
i += 2
end
if (n > 2)
# When n is greater than 2
result = n
end
return result
end
# Determine whether given number is unusual number or not
def is_unusual_no(number)
factor = -1
if (number > 0)
factor = self.largest_prime_factor(number)
end
if (factor > -1 && factor > Math.sqrt(number))
print("\n [", number ,"] is unusual number")
else
print("\n [", number ,"] is not unusual number")
end
end
end
def main()
obj = UnusualNumber.new()
number = 14
# Test case
obj.is_unusual_no(number)
number = 34
obj.is_unusual_no(number)
number = 50
obj.is_unusual_no(number)
end
main()
Output
[14] is unusual number
[34] is unusual number
[50] is not unusual number
/*
Scala program
Check if a number is an unusual number or not
*/
class UnusualNumber
{
def largest_prime_factor(number: Int): Int = {
var result: Int = -1;
var n: Int = number;
// Execute this loop until, when the n is a odd number
while (n % 2 == 0)
{
result = 2;
n = (n / 2).toInt;
}
var sqrt_value: Int = (Math.sqrt(n)).toInt;
// Loop controlling variable
var i: Int = 3;
while (i <= sqrt_value)
{
while (n % i == 0)
{
// When [i] is factor of n
result = i;
n = (n / i).toInt;
}
i += 2;
}
if (n > 2)
{
// When n is greater than 2
result = n;
}
return result;
}
// Determine whether given number is unusual number or not
def is_unusual_no(number: Int): Unit = {
var factor: Int = -1;
if (number > 0)
{
factor = largest_prime_factor(number);
}
if (factor > -1 && factor > Math.sqrt(number))
{
print("\n [" + number + "] is unusual number");
}
else
{
print("\n [" + number + "] is not unusual number");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: UnusualNumber = new UnusualNumber();
var number: Int = 14;
//Test case
obj.is_unusual_no(number);
number = 34;
obj.is_unusual_no(number);
number = 50;
obj.is_unusual_no(number);
}
}
Output
[14] is unusual number
[34] is unusual number
[50] is not unusual number
import Foundation
/*
Swift 4 program
Check if a number is an unusual number or not
*/
class UnusualNumber
{
func largest_prime_factor(_ number: Int) -> Int
{
var result: Int = -1;
var n: Int = number;
// Execute this loop until, when the n is a odd number
while (n % 2 == 0)
{
result = 2;
n = n / 2;
}
let sqrt_value: Int = Int(sqrt(Double(n)));
// Loop controlling variable
var i: Int = 3;
while (i <= sqrt_value)
{
while (n % i == 0)
{
// When [i]is factor of n
result = i;
n = n / i;
}
i += 2;
}
if (n > 2)
{
// When n is greater than 2
result = n;
}
return result;
}
// Determine whether given number is unusual number or not
func is_unusual_no(_ number: Int)
{
var factor: Int = -1;
if (number > 0)
{
factor = self.largest_prime_factor(number);
}
if (factor > -1 && Double(factor) > sqrt(Double(number)))
{
print("\n [", number ,"] is unusual number", terminator: "");
}
else
{
print("\n [", number ,"] is not unusual number", terminator: "");
}
}
}
func main()
{
let obj: UnusualNumber = UnusualNumber();
var number: Int = 14;
//Test case
obj.is_unusual_no(number);
number = 34;
obj.is_unusual_no(number);
number = 50;
obj.is_unusual_no(number);
}
main();
Output
[ 14 ] is unusual number
[ 34 ] is unusual number
[ 50 ] is not unusual number
Program Explanation
- The program starts with the standard C library includes and the
main
function. - The
largest_prime_factor(number)
function implements the algorithm explained above to find the largest prime factor of the given number. - The
is_unusual_no(number)
function takes an integernumber
as input and calls thelargest_prime_factor
function to get the largest prime factor of the number. - It then checks whether the obtained largest prime factor is greater than the square root of the given number. If it is, the number is considered unusual and the corresponding message is printed.
- The
main
function tests theis_unusual_no
function with three example test cases: 14, 34, and 50. - The output of the program is explained in the comments below the test cases.
Resultant Output Explanation
- For the number 14, the program finds its largest prime factor as 7, which is greater than the square root of 14. So, it correctly identifies 14 as an unusual number.
- For the number 34, the program finds its largest prime factor as 17, which is greater than the square root of 34. Thus, it correctly identifies 34 as an unusual number.
- For the number 50, the program finds its largest prime factor as 5, which is not greater than the square root of 50. Therefore, it correctly identifies 50 as not being an unusual number.
Time Complexity
The time complexity of finding the largest prime factor of a number n
in the function
largest_prime_factor
can be approximated to O(sqrt(n)). The loop runs up to the square root of the
updated number (n
) to find all the prime factors. Since the square root is the largest factor of a
number, this algorithm is reasonably efficient for determining the largest prime factor. For the
is_unusual_no
function, the time complexity is mainly determined by the
largest_prime_factor
function, so it remains O(sqrt(n)) as well.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment