sphenic n o Algorithm
The Sphenic Number Algorithm is a mathematical technique used to identify and generate sphenic numbers, which are the product of three distinct prime factors. Sphenic numbers hold a particular interest for mathematicians and number theorists due to their unique properties and applications in various fields. The algorithm revolves around the process of prime factorization, which involves breaking down a given number into the product of its prime factors. To be a sphenic number, the product must consist of exactly three distinct prime factors, meaning each of the factors is a prime number and occurs only once in the factorization.
To implement the Sphenic Number Algorithm, one must first generate a list of prime numbers up to a certain limit, typically using a prime-generating algorithm such as the Sieve of Eratosthenes. Once the prime numbers are obtained, the algorithm iterates through all possible combinations of three distinct primes, multiplying them together to generate potential sphenic numbers. During this process, the algorithm checks if the product of the three primes is within the desired range and ensures that the prime factors are distinct. If the conditions are met, the number is considered a sphenic number and is added to the list of sphenic numbers. The algorithm continues this process until all possible combinations of prime factors have been tested, ultimately generating a comprehensive list of sphenic numbers within the specified range.
//CODE ADAPTED FROM OTHER WEBSITE.
// C++ program to check whether a number is a
// Sphenic number or not
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000;
// Create a vector to store least primes.
// Initialize all entries as 0.
vector<int> least_pf(MAX, 0);
// This function fills values in least_pf[].
// such that the value of least_pf[i] stores
// smallest prime factor of i.
// This function is based on sieve of Eratosthenes
void leastPrimeFactor(int n)
{
// Least prime factor for 1 is 1
least_pf[1] = 1;
// Store least prime factor for all other
// numbers.
for (int i = 2; i <= n; i++)
{
// least_pf[i] == 0 means i is prime
if (least_pf[i] == 0)
{
// Initializing prime number as its own
// least prime factor.
least_pf[i] = i;
// Mark 'i' as a divisor for all its
// multiples that are not already marked
for (int j = 2*i; j <= n; j += i)
if (least_pf[j] == 0)
least_pf[j] = i;
}
}
}
// Function returns true if n is a sphenic number and
// No otherwise
bool isSphenic(int n)
{
// Stores three prime factors of n. We have at-most
// three elements in s.
set<int> s;
// Keep finding least prime factors until n becomes 1
while (n > 1)
{
// Find least prime factor of current value of n.
int lpf = least_pf[n];
// We store current size of s to check if a prime
// factor repeats
int init_size = s.size();
// Insert least prime factor of current value of n
s.insert(lpf);
// If either lpf repeats or number of lpfs becomes
// more than 3, then return false.
if (s.size() == init_size || s.size() > 3)
// same prime divides the
// number more than once
return false;
// Divide n by lpf
n /= lpf;
}
// Return true if size of set is 3
return (s.size() == 3);
}
int main()
{
leastPrimeFactor(MAX);
for (int i=1; i<100; i++)
if (isSphenic(i))
cout << i << " ";
return 0;
}
