Optimization of the maximum Prime Factor algorithm

Question

I am trying to improve this interesting algorithm as much as I can.

Now I have this:

using System;

class Program
{

    static void Main()
    {
        ulong num, largest_pFact;
        uint i = 2;
        string strNum;

        Console.Write("Enter number: ");
        strNum = Console.ReadLine();
        num = ulong.Parse(strNum);
        largest_pFact = num;


        while (i < Math.Sqrt((double) largest_pFact))
        {
            if (i % 2 != 0 | i == 2) {
                if (largest_pFact % i == 0) 
                    largest_pFact /= i;
            }

            i++;
        }

        Console.WriteLine("Largest prime factor of {0} is: {1}", num, largest_pFact);
        Console.ReadLine();

    }
}

So any ideas?

Thank!

EDIT : I implemented the Ben algorithm, thanks eveyone for your help!

Answer 1

I have a faster algorithm here .

It eliminates the square root and correctly processes repetitive factors.

Optimization:

static private ulong maxfactor (ulong n)
{
    unchecked
    {
        while (n > 3 && 0 == (n & 1)) n >>= 1;

        uint k = 3;
        ulong k2 = 9;
        ulong delta = 16;
        while (k2 <= n)
        {
            if (n % k == 0)
            {
                n /= k;
            }
            else
            {
                k += 2;
                if (k2 + delta < delta) return n;
                k2 += delta;
                delta += 8;
            }
        }
    }

    return n;
}

Here is a working demo: http://ideone.com/SIcIL

Answer 2

-Store Math.Sqrt((double) _pFact) , . , , . <= .

- . = 2, 3, 2 . , = 2,3 , = 6n + 1 6n-1.

Answer 3

, 2 , , . , int, uint, :

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
while (i < Math.Sqrt((double) largest_pFact)) {
  if (i % 2 != 0) {
    if (largest_pFact % i == 0) {
      largest_pFact /= i;
    }
  }
  i++;
}

, :

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  if (i % 2 != 0) {
    if (largest_pFact % i == 0) {
      largest_pFact /= i;
    }
  }
  i++;
}

i , :

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  if (largest_pFact % i == 0) {
    largest_pFact /= i;
  }
  i += 2;
}

, , while if , :

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  while (largest_pFact % i == 0) {
    largest_pFact /= i;
  }
  i += 2;
}

Answer 4

, Math.Sqrt .

    int root = Math.Sqrt((double) largest_pFact);

    while (i < root)
    {
        if ((i % 2 != 0 | i == 2) && largest_pFact % i == 0) {
            largest_pFact /= i;
            root = Math.Sqrt((double) largest_pFact);
        }

        i++;
    }

Answer 5

:

• num/2
• , num

.

edit num/2 sqrt

Answer 6

sqrt (num) 2, num/2. ( -) , sqrt (num).

: 15, int (sqrt (15)) == 3   15/3 = 5, "5", 3 7.

Answer 7

This is my attempt, but I'm not sure if this is correct ... Dosed work with huge numbers: ((

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PrimeFactor
{
class Program
{
    static void Main(string[] args)
    {

        Int64 i, y =65;
        List<Int64> PrimeFactor = new List<Int64>();
        for (i = 2; i <65; i++)
        {
            if (y % i == 0)
            {
                y = y / i;
                PrimeFactor.Add(i);



                }
            }
        PrimeFactor.Sort();

        foreach (Int64 j in PrimeFactor)
        {
            Console.WriteLine(j);
        }

        }


        }
        }