Sphenic Number
A Sphenic Number is a positive integer n which is a product of exactly three distinct primes. The first few sphenic numbers are 30, 42, 66, 70, 78, 102, 105, 110, 114, …
Given a number n, determine whether it is a Sphenic Number or not.
Examples:
Input: 30
Output : Yes
Explanation: 30 is the smallest Sphenic number,
30 = 2 × 3 × 5 the product of the smallest three primesInput: 60
Output : No
Explanation: 60 = 22 x 3 x 5 has exactly 3 prime factors but is not a sphenic number
The sphenic number can be checked by the fact that every sphenic number will have exactly 8 divisors SPHENIC NUMBER
So first We will try to find if the number has exactly 8 divisors if not then the simple answer is no. If there are exactly 8 divisors then we will confirm whether the first 3 digits after 1 are prime or not.
Eg. 30 (sphenic number)
30=p*q*r(i.e p,q and r are three distinct prime no and their product are 30)
the set of divisor is (1,2,3,5,6,10,15,30).
Below is the implementation of the idea.
// C++ program to check whether a number is a
// Sphenic number or not
#include<bits/stdc++.h>
using namespace std;
//create a global array of size 10001;
bool arr[1001];
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes.
void simpleSieve()
{
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
memset(arr,true,sizeof(arr));
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for(int p=2;p*p<1001;p++)
{
// If p is not changed, then it is a prime
if(arr[p])
{// Update all multiples of p
for(int i=p*2;i<1001;i=i+p)
arr[i]=false;
}
}
}
int find_sphene(int N)
{
int arr1[8]={0}; //to store the 8 divisors
int count=0; //to count the number of divisor
int j=0;
for(int i=1;i<=N;i++)
{
if(N%i==0 &&count<9)
{
count++;
arr1[j++]=i;
}
}
//finally check if there re 8 divisor and all the numbers are distinct prime no return 1
//else return 0
if(count==8 && (arr[arr1[1]] && arr[arr1[2]] && arr[arr1[3]]))
return 1;
return 0;
}
// Driver program to test above function
int main()
{
int n = 60;
simpleSieve();
int ans=find_sphene(n);
if(ans)
cout<<"Yes";
else
cout<<"NO";
}
// Java program to check whether a number is a
// Sphenic number or not
import java.util.*;
class GFG
{
// create a global array of size 10001;
static boolean []arr = new boolean[1001];
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes.
static void simpleSieve()
{
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
Arrays.fill(arr, true);
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for(int p = 2; p * p < 1001; p++)
{
// If p is not changed, then it is a prime
if(arr[p])
{
// Update all multiples of p
for(int i = p * 2; i < 1001; i = i + p)
arr[i] = false;
}
}
}
static int find_sphene(int N)
{
int []arr1 = new int[8]; // to store the 8 divisors
int count = 0; // to count the number of divisor
int j = 0;
for(int i = 1; i <= N; i++)
{
if(N % i == 0 && count < 8)
{
count++;
arr1[j++] = i;
}
}
// finally check if there re 8 divisor and
// all the numbers are distinct prime no return 1
// else return 0);
if(count == 8 && (arr[arr1[1]] && arr[arr1[2]] && arr[arr1[3]]))
return 1;
return 0;
}
// Driver code
public static void main(String[] args)
{
int n = 60;
simpleSieve();
int ans = find_sphene(n);
if(ans == 1)
System.out.print("Yes");
else
System.out.print("NO");
}
}
// This code is contributed by aashish1995
// C# program to check whether a number
// is a Sphenic number or not
using System;
class GFG{
// Create a global array of size 10001;
static bool []arr = new bool[1001];
// This functions finds all primes smaller than
// 'limit'. Using simple sieve of eratosthenes.
static void simpleSieve()
{
// Initialize all entries of it as true.
// A value in mark[p] will finally be
// false if 'p' is Not a prime, else true.
for(int i = 0;i<1001;i++)
arr[i] = true;
// One by one traverse all numbers so
// that their multiples can be marked
// as composite.
for(int p = 2; p * p < 1001; p++)
{
// If p is not changed, then it
// is a prime
if (arr[p])
{
// Update all multiples of p
for(int i = p * 2; i < 1001; i = i + p)
arr[i] = false;
}
}
}
static int find_sphene(int N)
{
// To store the 8 divisors
int []arr1 = new int[8];
// To count the number of divisor
int count = 0;
int j = 0;
for(int i = 1; i <= N; i++)
{
if (N % i == 0 && count < 8)
{
count++;
arr1[j++] = i;
}
}
// Finally check if there re 8 divisor
// and all the numbers are distinct prime
// no return 1 else return 0);
if (count == 8 && (arr[arr1[1]] &&
arr[arr1[2]] && arr[arr1[3]]))
return 1;
return 0;
}
// Driver code
public static void Main(String[] args)
{
int n = 60;
simpleSieve();
int ans = find_sphene(n);
if (ans == 1)
Console.Write("Yes");
else
Console.Write("NO");
}
}
// This code is contributed by aashish1995
<script>
// javascript program to check whether a number is a
// Sphenic number or not
// create a global array of size 10001;
// initialize all entries of it as true. A value
// in mark[p] will finally be false if 'p' is Not
// a prime, else true.
let arr = Array(1001).fill(true);
// This functions finds all primes smaller than 'limit'
// using simple sieve of eratosthenes.
function simpleSieve()
{
// One by one traverse all numbers so that their
// multiples can be marked as composite.
for (let p = 2; p * p < 1001; p++) {
// If p is not changed, then it is a prime
if (arr[p]) {
// Update all multiples of p
for (let i = p * 2; i < 1001; i = i + p)
arr[i] = false;
}
}
}
function find_sphene(N) {
var arr1 = Array(8).fill(0); // to store the 8 divisors
var count = 0; // to count the number of divisor
var j = 0;
for (let i = 1; i <= N; i++) {
if (N % i == 0 && count < 8) {
count++;
arr1[j++] = i;
}
}
// finally check if there re 8 divisor and
// all the numbers are distinct prime no return 1
// else return 0);
if (count == 8 && (arr[arr1[1]] && arr[arr1[2]] && arr[arr1[3]]))
return 1;
return 0;
}
// Driver code
var n = 60;
simpleSieve();
var ans = find_sphene(n);
if (ans == 1)
document.write("Yes");
else
document.write("NO");
// This code is contributed by aashish1995
</script>
def simpleSieve():
# Initialize all entries of arr as True
arr = [True] * 1001
# One by one traverse all numbers so that their
# multiples can be marked as composite
for p in range(2, int(1001 ** 0.5) + 1):
# If p is not changed, then it is a prime
if arr[p]:
# Update all multiples of p
for i in range(p * 2, 1001, p):
arr[i] = False
return arr
def find_sphene(N):
arr = simpleSieve()
arr1 = [0] * 8 # to store the 8 divisors
count = 0 # to count the number of divisors
j = 0
for i in range(1, N + 1):
if N % i == 0 and count < 9:
count += 1
arr1[j] = i
j += 1
# finally check if there are 8 divisors and all the numbers are distinct prime no return 1
# else return 0
if count == 8 and all(arr[arr1[i]] for i in range(1, 4)):
return 1
return 0
# Driver program to test above function
if __name__ == "__main__":
n = 60
ans = find_sphene(n)
if ans:
print("Yes")
else:
print("No")
Output:
NO
Time Complexity: O(?p log p)
Auxiliary Space: O(n)
References:
1. OEIS
2. https://en.wikipedia.org/wiki/Sphenic_number
Contact Us