Sphenic Number In C++

In this post, we are going to explore Sphenic Numbers in C++. Prior to delving into Sphenic Numbers in C++, it's essential to understand the concepts of procedures, illustrations, time complexity, and space complexity.

What is the Sphenic Number in C++?

An integer that is positive and the result of precisely three distinct prime numbers is known as a sphenic number. For instance, 30 qualifies as a sphenic number since it can be broken down into three distinct prime numbers: 2×3×5, among others. Likewise, 42 (2×3×7), 66 (2×3×11), and 70 (2×5×7) are additional illustrations of sphenic numbers. These numbers hold importance due to their demonstration of a distinctive factorization characteristic, where precisely three prime factors play a role in their formation.

It stipulates that a Sphenic number is characterized by having exactly eight divisors. Upon prime factorization of a Sphenic number, all feasible combinations of its prime factors, encompassing both the number 1 and the number itself, are utilized in generating the divisors of the number. For instance, if n=p1×p2×p3 and p1, p2, p3 represent distinct prime numbers, the "𝑝1,2,𝑝3,𝑝1×𝑝2,𝑝1×𝑝3,𝑝2×𝑝3,𝑝1×𝑝2×𝑝3" will constitute the divisors of n, amounting to precisely eight divisors.

Steps to check if a Number is Sphenic:

• ✅ Divisor Count: Checking to determine if the number has exactly eight divisors is the first step. A number is not a Sphenic number if it has more or fewer than eight divisors. The simplest way to eliminate non-Sphenic numbers is to use this check.
• ✅ Prime Validation: The next step is to verify that the first three divisors (after 1) are unique prime numbers if the number has precisely eight divisors. The prime factors of the number will be these primes. Certainly, the number is a sphenic number if all three are prime.
• ✅ Consider the number 30 as an example: There are precisely eight divisors of 30 and they are 1, 2, 3, 5, 6, 10, 15, and 30. The fact that 2, 3, and 5 are unique primes among these divisors proves that 30 is a Sphenic number.
• ✅ In contrast, a number like 12: Even though 2 and 3 are prime factors, 12 cannot be a sphenic number because its divisors are 1, 2, 3, 4, 6, and 12, which are only six divisors. Consequently, we first check the divisor count to see if a number is a Sphenic number, and if it is 8, we next confirm the primality of the first three divisors. By using their distinct prime factorization features, this method ensures that we correctly identify Sphenic numbers.

Example:

Let's consider an example to demonstrate the concept of Sphenic Number in C++.

#include <iostream>
#include <cstring>
using namespace std;
bool isPrime[1001];
void sieveOfEratosthenes() 
{
    memset(isPrime, true, sizeof(isPrime));
    for (int i = 2; i * i <= 1000; i++)
    {
        if (isPrime[i]) 
        {
            for (int j = i * 2; j <= 1000; j += i) 
            {
                isPrime[j] = false;
            }
        }
    }
}
int checkSphenicNumber(int number) 
{
    int divisors[8] = {0};
    int divisorCount = 0;
    int divisorIndex = 0;
    for (int i = 1; i <= number; i++)
    {
        if (number % i == 0 && divisorCount < 9)
        {
            divisors[divisorIndex++] = i;
            divisorCount++;
        }
    }
    if (divisorCount == 8 && isPrime[divisors[1]] && isPrime[divisors[2]] && isPrime[divisors[3]])
    {
        return 1;
    }
    return 0;
}
int main()
{
    int inputNumber;
    cout << "Enter a number to check if it is a Sphenic number: ";
    cin >> inputNumber;
    sieveOfEratosthenes();
    int result = checkSphenicNumber(inputNumber);
    if (result)
    {
        cout << "Yes, the number is a Sphenic number." << endl;
    }
    else 
    {
        cout << "No, the number is not a Sphenic number." << endl;
    }
    return 0;
}

Output:

Enter a number to check if it is a Sphenic number: 30
Yes, the number is a Sphenic number.

Explanation:

This C++ software verifies if a provided number possesses precisely three unique prime divisors, making it a Sphenic number. Initially, it creates a list of prime numbers up to 1000 utilizing the Sieve of Eratosthenes to distinguish non-prime numbers within the isPrime array. Subsequently, the checkSphenicNumber function enumerates all divisors of the given number. A number qualifies as a Sphenic number if it has precisely eight divisors, with the initial three being distinct prime numbers (verified by the isPrime array). Within the main function, the user is prompted to input a number, which is then passed to the checkSphenicNumber function to ascertain if it meets the Sphenic number conditions.

The software indicates whether a given number is classified as a Sphenic number or not according to its outcome. An array is employed to retain the prime status of each number, allowing the application to efficiently identify prime numbers and their corresponding divisors.

Complexity Analysis:

• ✅ Time Complexity: O(p log p): In order to determine prime numbers, the sieve algorithm iterates through each prime number up to p, designating multiples as non-prime. This results in a time complexity of O(plogp).
• ✅ Auxiliary Space: O(n): The isPrime array, which maintains stores of the prime status for every integer up to n (in this case, 1000), causes the auxiliary space complexity to be O(n). As a result, the quantity of space used is proportional to the size of the input range.