Print first N Mosaic numbers in Java
A Mosaic number is derived from the prime factorization of an integer N. The prime factorization of N is defined as the product of different prime numbers raised to their respective powers. The Mosaic number corresponding to N is calculated by multiplying each prime raised to its corresponding power. In basic terms, it is the product of prime components that maintain their multiplicities.
Example:
Input: N = 6
Output: First 6 Mosaic numbers: 1 2 3 4 5 6
Explanation:
1. Prime factorization of 1: None (because one is not a prime number).
2. The prime factorization of 2 is 2^1.
3. The prime factorization of 3 is 3^1.
4. The prime factorization of 4 is 2^2.
5. The prime factorization of 5 is 5^1.
6. The prime factorization of 6 is 2^1 * 3^1.
Therefore, the first six Mosaic numbers are 1, 2, 3, 4, 5, and 6.
Iterative Approach
Algorithm
Step 1: Create a variable to keep track of the current integer (beginning at 1).
Step 2: Repeat for the required number of mosaics (N).
Step 3: Calculate the Mosaic number for each integer using prime factorization.
Step 4: Print each integer, along with its calculated Mosaic number.
Step 5: Go to the next integer.
Step 6: Repeat steps 3 to 5 until N mosaic numbers are printed.
FileName: MosaicNumbers.java
public class MosaicNumbers { // Function to return the nth mosaic number static int getMosaicNumber(int num) { int mosaicNumber = 1; // Iterate from 2 to the number for (int i = 2; i <= num; i++) { // If i is the factor of n if (num % i == 0 && num > 0) { int count = 0; // Find the count where i^count // is a factor of n for (; num % i == 0; num /= i, count++) ; // Multiply the answer with // count and i mosaicNumber *= count * i; } } // Return the answer return mosaicNumber; } // Function to print first N Mosaic numbers static void printFirstNMosaicNumbers(int N) { System.out.print("First " + N + " Mosaic numbers: "); for (int i = 1; i <= N; i++) System.out.print(getMosaicNumber(i) + " "); } // Driver code public static void main(String[] args) { int N = 6; printFirstNMosaicNumbers(N); } }
Output:
First 6 Mosaic numbers: 1 2 3 4 5 6
Complexity Analysis: The time complexity is O(N * num), where N is the number of mosaic numbers to print and num is the maximum value of them and the space complexity is O(1) since the program uses the same amount of memory regardless of the input size.
Optimized Factorization Approach
Algorithm
Step 1: Create an empty list to store prime factors and counts.
Step 2: Iterate from 2 to the provided number's square root, counting the prime elements.
Step 3: Use an ArrayList to store factor counts.
Step 4: Return the ArrayList of prime factors.
Step 5: Determine the prime factorization of any number from 1 to N.
Step 6: Calculate and print the mosaic number.
FileName: MosaicNumbers1.java
import java.util.ArrayList; public class MosaicNumbers1 { // Function to generate prime factorization of a number static ArrayListprimeFactorization(int n) { ArrayList factors = new ArrayList<>(); for (int i = 2; i * i <= n; i++) { int count = 0; while (n % i == 0) { n /= i; count++; } if (count > 0) factors.add(new int[]{i, count}); } if (n > 1) factors.add(new int[]{n, 1}); return factors; } // Function to print first N Mosaic numbers static void printMosaicNumbers(int N) { int count = 0; System.out.print("First " + N + " Mosaic numbers: "); for (int num = 1; count < N; num++) { ArrayList factors = primeFactorization(num); int mosaic = 1; for (int[] factor : factors) { mosaic *= factor[0] * factor[1]; } System.out.print(mosaic + " "); count++; } } public static void main(String[] args) { int N = 6; printMosaicNumbers(N); } }
Output:
First 6 Mosaic numbers: 1 2 3 4 5 6
Complexity Analysis: The time complexity is O(N * sqrt(num)), where N is the number of Mosaic numbers to print and num is the maximum value among them. The space complexity is also O(N * sqrt(num)), taking into account the storage requirements for each number's prime factorization.