Posted on by Kalkicode
Code Number

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:

  1. 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.

  2. 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.

  3. 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)
  1. Define a function largest_prime_factor(number) that takes an integer as input and returns the largest prime factor of that number.
  2. Initialize a variable result to -1. This variable will store the largest prime factor.
  3. Divide the input number number by 2 until it becomes an odd number, and at each step, update the result to 2 (since 2 is the smallest prime factor). This step ensures that the number becomes odd.
  4. Calculate the square root of the updated number and store it in sqrt_value.
  5. Starting from 3, iterate over all odd numbers up to sqrt_value.
  6. For each odd number i, check if it is a factor of the updated number (number). If it is a factor, update the result to i and divide the number by i.
  7. Repeat step 6 until there are no more factors of i in the number.
  8. If the remaining number (n) after the loop is greater than 2, update the result to n.
  9. 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

  1. The program starts with the standard C library includes and the main function.
  2. The largest_prime_factor(number) function implements the algorithm explained above to find the largest prime factor of the given number.
  3. The is_unusual_no(number) function takes an integer number as input and calls the largest_prime_factor function to get the largest prime factor of the number.
  4. 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.
  5. The main function tests the is_unusual_no function with three example test cases: 14, 34, and 50.
  6. The output of the program is explained in the comments below the test cases.

Resultant Output Explanation

  1. 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.
  2. 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.
  3. 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.

Comment

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