How to find Prime Factors till a limit

In this article, let's try to find a solution for the coding problem - Print all the possible prime factors for all the numbers till the given limit.

Let’s assume we are given a number n. we need to print all the numbers till the given number n, such that for every number if there exists a prime factor, we need to print those prime factors instead of that number in the set.

For example, if we are given the number as 10. we need to print the output as: 1 2 3 2 5 2 3 7 2 3 2 5

The input is an upper limit, until which we will move and print all the prime factors for every number we have visited.

The output for the program is as below –

1
2
3
2 <- for 4, since 4 = 2 x 2
5
2 3 <- for 6, since 6 = 2 x 3
7
2 <- for 8, since 8 = 2 x 4
3 <- for 9, since 9 = 3 x 3
2 5 <- for 10, since 10 = 2 x 5

How do we solve this?

Let’s try to approach it like this:

  1. Maintain a list of primes we have encountered through out the loop, say primes.
  2. For every element in the series till the limit n, say x
  3. maintain a flag isPrime to check if there was a factor or not, set to true
  4. Loop from 2 till the number x, with a counter i
  5. Check if there is any i that is a factor of x
  6. if there is this i in the primes, print the number i
  7. unset the flag isPrime, since we know that i is a factor of x
  8. End of the loop
  9. if the counter i is equal to x and isPrime is still set to true, add the current number x to the set of primes we’re maintaining.
  10. The same process is repeated for all the numbers till the limit n

Code in C#

public class PrimeFactorBuzz
{
    HashSet<int> primes = new HashSet<int>();

    public void DoPrimeFactors(int n)
    {
        for (int i = 1; i <= n; i++)
        {
            PrimeFactor(i);
        }
    }

    public void PrimeFactor(int number)
    {
        bool isPrime = true;
        int up = number;

        int i = 2;
        while (i < up)
        {
            if (number % i == 0)
            {
                if (primes.Contains(i))
                {
                    Console.Write($"{i}"); isPrime = false;
                }
            }
            i++;
        }
        if (number == 1) Console.Write($"{number}");

        if (i == up && isPrime)
        {
            Console.Write($"{number} "); primes.Add(number);
        }
    }
}
Ram
Ram

I'm a full-stack developer and a software enthusiast who likes to play around with cloud and tech stack out of curiosity. You can connect with me on Medium, Twitter or LinkedIn.

Privacy Overview
Referbruv

This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.

Strictly Necessary Cookies

Strictly Necessary Cookie should be enabled at all times so that we can save your preferences for cookie settings.

3rd Party Cookies

This website uses Google Analytics to collect anonymous information such as the number of visitors to the site, and the most popular pages.

Keeping this cookie enabled helps us to improve our website.