C＃，找到一个数的最大素数因子 [英] C#, finding the largest prime factor of a number

问题描述

我在编程新我在练我的C＃编程技能。我的应用是为了找到由用户输入的号码中最大的首要因素。但我的应用程序没有返回正确的答案，我真的不知道问题出在哪里。你能帮我么？

 使用系统; 
使用System.Collections.Generic; 
使用System.Linq的; 
使用System.Text; 
 
命名ConsoleApplication1 
 {
类节目
 {
静态无效的主要（字串[] args）
 {
控制台。的WriteLine（。Calcular因素的Máximo普里莫·N个去上课60 5）; 
 Console.Write（联合国Escriba NUMERO：）; 
长NUM = Convert.ToInt64（到Console.ReadLine（））; 
长MFP = MAXFACTOR（NUM）; 
 Console.WriteLine（厄尔尼诺马克西莫因素普里莫ES：+ NUM）; 
 Console.Read（）; 
} 
静态私人长期MAXFACTOR（N久）
 {
长M = 1; 
布尔EN = FALSE; 
为（长K = N / 2;！恩和放大器;&安培; K> 1; K--）
 {
如果（N％K = = 0&放大器;&安培;普里莫（k））的
 {
M = K; 
 EN =真实的; 
} 
} 
返回米; 
 
} 
静态专用布尔普里莫（长x）
 {
布尔SP = TRUE; 
为（长我= 2; I< = X / 2;我++）
 {
如果（X％我== 0）
 SP = FALSE; 
} 
返回SP; 
} 
} 
} 
  

解决方案

这会快很多，除去小的因素，直到残留物素。

 静态私人长期MAXFACTOR（长N）
 {
长K = 2; 
，而（K * K< = N）
 {
如果（N％K == 0）
 {
 N / = K; 
} 
，否则
 {
 ++ K表; 
} 
} 
 
返回N; 
} 
  

例如，如果n = 784，这并不9模运算而不是几个百。 。掰着指头甚至与开方限制仍然会做只是MAXFACTOR 21模OPS，并在普里莫另有十余

新的更优化的版本的here

I am new at programming and I am practicing my C# programming skills. My application is meant to find the largest prime factor of a number entered by the user. But my application is not returning the right answer and I dont really know where the problem is. Can you please help me?

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;
        }
    }
}

解决方案

It will be much faster to remove the small factors until the residue is prime.

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

    return n;
}

For example, if n = 784, this does 9 modulo operations instead of several hundred. Counting down even with the sqrt limit still would do 21 modulo ops just in maxfactor, and another dozen in primo.

New more optimized version here

这篇关于C＃，找到一个数的最大素数因子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！