Round #1002

Find the prime factorisation of 360.

To find the prime factorization of 360, we can start by dividing it by the smallest prime number, which is 2. ```csharp using System; class Program { static void Main() { int number = 360; int i = 2; while (i * i <= number) { if (number % i != 0) { i++; } else { number /= i; Console.Write(i + " "); } } if (number > 1) { Console.Write(number); } } } ``` When you run this program, it will output the prime factors of 360. The output will be: `2 2 2 3 3 5` So, the prime factorization of 360 is **2^3 * 3^2 * 5**.

To find the prime factorization of 360, we can use the following steps: ```csharp using System; using System.Collections.Generic; public class PrimeFactorization { public static List<(int, int)> Factorize(int n) { var factors = new List<(int, int)>(); int i = 2; while (i * i <= n) { int count = 0; while (n % i == 0) { n /= i; count++; } if (count > 0) { factors.Add((i, count)); } i++; } if (n > 1) { factors.Add((n, 1)); } return factors; } public static void Main(string[] args) { var factors = Factorize(360); Console.WriteLine("Prime factorization of 360:"); foreach (var factor in factors) { Console.WriteLine($"{factor.Item1}^{factor.Item2}"); } } } ``` This code will output the prime factorization of 360 as 2^3 * 3^2 * 5^1. The `Factorize` method works by dividing the input number `n` by the smallest prime number (2) as long as it's divisible. Then it increments the divisor until it finds the next number that can divide `n`, which will necessarily be a prime number. This process continues until `n` is reduced to 1. The list of factors is then returned, where each factor is a tuple containing the prime number and its exponent. In the `Main` method, we call `Factorize` with the input 360 and print out the resulting prime factorization. This implementation is based on the fundamental theorem of arithmetic, which states that every integer greater than 1 either is prime itself or can be factorized as a product of prime numbers in a unique way. Note: This implementation has a time complexity of O(sqrt(n)) due to the while loop that runs up to the square root of `n`. This is sufficient for most practical purposes, but for very large numbers, more efficient algorithms like the Sieve of Eratosthenes or the Miller-Rabin primality test may be needed.