CODEWITHSUNDEEP
c#for-loopif-statementprime-factoring
Qcom
Qcom

Reputation: 19163

C# largest prime factor with modulo?

I was wondering if it is possible to find the largest prime factor of a number by using modulos in C#. In other words, if i % x == 0 then we could break a for loop or something like that, where x is equal to all natural numbers below our i value.

How would I specify the all natural numbers below our i value as equal to our x variable? It becomes a little tedious to write out conditionals for every single integer if you know what I'm saying.

By the way, I'm sure there is a far easier way to do this in C#, so please let me know about it if you have an idea, but I'd also like to try and solve it this way, just to see if I can do it with my beginner knowledge.

Here is my current code if you want to see what I have so far:

static void Main()
{
    int largestPrimeFactor = 0;

    for (long i = 98739853; i <= 98739853; i--)
    {
        if (true)
        {
            largestPrimeFactor += (int) i;
            break;
        }
    }

    Console.WriteLine(largestPrimeFactor);
    Console.ReadLine();
}

Upvotes: 1

Views: 1135

Answers (3)

Ichibann
Ichibann

Reputation: 4451

If I were to do this using loop and modulos I would do:

long number = 98739853;
long biggestdiv = number;

while(number%2==0) //get rid of even numbers
    number/=2;

long divisor = 3;

if(number!=1)
while(divisor!=number)
{
    while(number%divisor==0)
    {
        number/=divisor;
        biggestdiv = divisor;
    }

    divisor+=2;
}

In the end, biggestdiv would be the largest prime factor.

Note: This code is written directly in browser. I didn't try to compile or run it. This is only for showing my concept. There might be algorithm mistakes. It they are, let me know. I'm aware of the fact that it is not optimized at all (I think Sieve is the best for this).

EDIT:
fixed: previous code would return 1 when number were prime.
fixed: previous code would end in loop leading to overflow of divisor where number were power of 2

Upvotes: 5

Joel Coehoorn
Joel Coehoorn

Reputation: 415665

Ooh, this sounds like a fun use for iterator blocks. Don't turn this in to your professor, though:

private static List<int> primes = new List<int>() {2};
public static IEnumerable<int> Primes()
{
    int p;
    foreach(int i in primes) {p = i; yield return p;}

    while (p < int.MaxValue)
    {
       p++;

       if (!primes.Any(i => p % i ==0))
       {
           primes.Add(p);
           yield return p;
       }
    }          
}

public int LargestPrimeFactor(int n)
{
     return Primes.TakeWhile(p => p <= Math.Sqrt(n)).Where(p => n % p == 0).Last();
}

Upvotes: 3

winwaed
winwaed

Reputation: 7801

I'm not sure quite what your question is: perhaps you need a loop over the numbers? However there are two clear problems with your code:

  • Your for loop has the same stop and end value. Ie it will run once and once only

  • You have a break before the largestPrimeFactor sum. This sum will NEVER execute, because break will stop the for loop ( and hence execution of that block). The compiler should be giving a warning that this sum is unreachable.

Upvotes: 1

Related Questions