Print out the successful development of prime numbers from small to large

user_13883033 0
Viewed 434

Given any natural number N> 1 (previously assigned). Print out the successful development of prime numbers from small to large.
Example: 9 --> 3 * 3
12 --> 2 * 2 * 3

My idea is find all GCD and add to list int, and write a function isPrimeNumber(int n), browse List< int > and check if isPrimeNumber().

But I can't solve problem print out the successful development of prime numbers from small to large

Here is what I tried

static void Main(string[] args)
{
    Console.WriteLine("Enter n: ");
    int n = Convert.ToInt32(Console.ReadLine());
    List<int> arr = new List<int>();

    for (int i = 1; i <= n; i++)
    {
        if (n % i == 0)
        {
            arr.Add(i);
        }
    }

    /* I need Print out the successful development of prime numbers from small to large here */

}

static bool isPrimeNumber(int n)
{
    if (n < 2)
    {
        return false;
    }

    for (int i = 2; i <= Math.Sqrt(n); i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }

    return true;
}
c#
3 Answers

I solved it
Here is code

static void lesson6()
        {
            Console.WriteLine("Enter n: ");
            int n = Convert.ToInt32(Console.ReadLine());
            int a = n;
            List<int> arr = new List<int>();
            for (int i = 2; i <= n; i++)
            {
                while (n % i == 0)
                {
                    arr.Add(i);
                    n /= i;
                }
            }
            Console.Write($"{a} = ");
            int lastIndex = arr.Count - 1;
            for (int i = 0; i < arr.Count; i++)
            {
                if (i == lastIndex)
                {
                    Console.Write(arr[i]);
                }
                else
                {
                    Console.Write(arr[i] + "*");
                }

            }
        }
user_138830330

As pointed by derpirscher in the comment, there are several sources online with different approaches for integer factorization.

I recommend you to look for Trial Division algorithm, as it is the easier to understand, and is similar to your approach.

Based on the code you shared, there are some thing you should consider:

for (int i = 1; i <= n; i++)
{
    if (n % i == 0)
    {
        arr.Add(i);
    }
}

After finding that a prime is a divisor and appending to the list, you are going to the next number. However, a prime can figure many times in the factorization of a number. E.g: 12 -> { 2, 2, 3 }.

You need divide n by the prime and continue testing the until it is not a divisor anymore, then you can go test the next prime.

This way, your n is shrinking down each time you find a prime divisor, until it eventually become 1. Then you know you found all prime divisors.

user_29385260

As you posted your working solution for that, let me share a different implementation for that that is still simple to understand, but more efficient, because it only tests primes until it reaches the square root of n. After that, there will not be any other divisor, except the number n itself, if n is prime.

static IList<int> Factors(int num) {
  var result = new List<int>();
  // avoid scenarios like num=0, that would cause infinite loop
  if (num <= 1) {
    return result;
  }
  // testing with 2 outside the main loop, otherwise we would skip factor 3 
  // (2 * 2 > 3)
  while (num % 2 == 0) {
    result.Add(2);
    num /= 2;
  }
  // only test primes until sqrt(num)
  int i = 3;
  while (i * i <= num) {
    if (num % i == 0) {
      result.Add(i);
      num /= i;
    } else {
      i++;
    }
  }
  // if not 1 here, num is prime
  if (num > 1) {
    result.Add(num);
  }
  return result;
}
user_29385260
Related