Let’s understand the expected output.
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:
- Maintain a list of primes we have encountered through out the loop, say primes.
- For every element in the series till the limit n, say x
- maintain a flag isPrime to check if there was a factor or not, set to true
- Loop from 2 till the number x, with a counter i
- Check if there is any i that is a factor of x
- if there is this i in the primes, print the number i
- unset the flag isPrime, since we know that i is a factor of x
- End of the loop
- 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.
- 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);
}
}
}