1

我想知道是否可以通过在 C# 中使用模数来找到一个数字的最大素数。换句话说，如果i % x == 0那时我们可以打破一个for循环或类似的东西，其中x等于所有低于我们i值的自然数。

我将如何指定all natural numbers below our i value等于我们的 x 变量？如果你知道我在说什么，为每个整数写出条件会变得有点乏味。

顺便说一句，我确信在 C# 中有一种更简单的方法可以做到这一点，所以如果你有想法，请告诉我，但我也想尝试以这种方式解决它，只是为了看看如果我能用我的初学者知识做到这一点。

如果你想看看我到目前为止有什么，这是我当前的代码：

static void Main()
{
    int largestPrimeFactor = 0;

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

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

3 回答 3

6

如果我要使用循环和模数来做到这一点，我会这样做：

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

最后，biggestdiv 将是最大的主要因素。

注意：此代码是直接在浏览器中编写的。我没有尝试编译或运行它。这只是为了展示我的概念。可能存在算法错误。他们是，让我知道。我知道它根本没有优化（我认为 Sieve 最适合这个）。

编辑：
固定：以前的代码在number素数时会返回 1。
已修复：之前的代码将在循环中结束，导致2divisor的number幂溢出

于 2010-11-07T19:41:35.893 回答
3

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();
}
于 2010-11-07T19:48:08.490 回答
1

我不太确定您的问题是什么：也许您需要对数字进行循环？但是，您的代码有两个明显的问题：

  • 您的 for 循环具有相同的停止和结束值。即它只会运行一次

  • 在最大的PrimeFactor 总和之前有一个休息时间。这个总和将永远不会执行，因为 break 将停止 for 循环（并因此停止执行该块）。编译器应该警告这个总和是不可达的。

于 2010-11-07T19:27:39.497 回答