C#, Ermittlung des größten Primfaktors einer Zahl

Question

Ich bin neu im Programmieren und übe meine C#-Programmierkenntnisse. Meine Anwendung soll den größten Primfaktor einer vom Benutzer eingegebenen Zahl finden. Aber meine Anwendung gibt nicht die richtige Antwort zurück und ich weiß nicht wirklich, wo das Problem liegt. Können Sie mir bitte helfen?

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Calcular máximo factor primo de n. De 60 es 5.");
            Console.Write("Escriba un numero: ");
            long num = Convert.ToInt64(Console.ReadLine());
            long mfp = maxfactor(num);
            Console.WriteLine("El maximo factor primo es: " + num);
            Console.Read();
        }
        static private long maxfactor (long n)
        {
            long m=1 ;
            bool en= false;
            for (long k = n / 2; !en && k > 1; k--)
            {
                if (n % k == 0 && primo(k))
                {
                    m = k;
                    en = true;
                }
            }
            return m;

        }
        static private bool primo(long x)
        {
            bool sp = true;
            for (long i = 2; i <= x / 2; i++)
            {
                if (x % i == 0)
                    sp = false;
            }
            return sp;
        }
    }
}

Answer 1

Es wird viel schneller gehen, die kleinen Faktoren zu entfernen, bis die Rückstände beseitigt sind.

static private long maxfactor (long n)
{
    long k = 2;
    while (k * k <= n)
    {
        if (n % k == 0)
        {
            n /= k;
        }
        else
        {
            ++k;
        }
    }

    return n;
}

Wenn zum Beispiel n = 784 ist, werden 9 Modulo-Operationen statt mehrerer hundert durchgeführt. Das Abwärtszählen würde selbst mit der sqrt-Grenze immer noch 21 Modulo-Operationen allein in maxfactor und ein weiteres Dutzend in primo ergeben.

Neue, optimierte Version aquí

Answer 2

Console.WriteLine("El maximo factor primo es: " + mfp);

anstelle von

Console.WriteLine("El maximo factor primo es: " + num);

Answer 3

Haben Sie eine Bedingung (!en), die dafür sorgt, dass nur bis zum ersten Primfaktor gezählt wird. Außerdem können Sie die Grenzen von n/2 auf sqrt(n)+1 reduzieren

Answer 4

Catalin DICU hat Ihre Frage bereits beantwortet, aber Sie haben einige nicht-idiomatische Konstrukte in Ihrem Code, die Sie wahrscheinlich nach Refactoring suchen sollten. Zum Beispiel, in Ihrem maxfactor Methode brauchen Sie die "en"-Bedingung nicht, sondern geben einfach den Wert zurück, sobald Sie ihn gefunden haben:

static private long maxfactor (long n)
{
    for (long k = n / 2; k > 1; k--)
    {
        if (n % k == 0 && primo(k))
        {
            return k;
        }
    }

    // no factors found
    return 1;
}

Ähnliches gilt für Ihre primo Methode, können Sie einfach false sobald Sie einen Faktor gefunden haben.

Answer 5

Hier ist eine f#-Version für diese:

let lpf n =
    let rec loop n = function        
        |k when k*k >= n -> n
        |k when n % k = 0I -> loop (n/k) k
        |k -> loop n (k+1I)
    loop n 2I