时间戳

首页 > 解决方案 > 尝试一个问题，但我编写的代码没有给出大量的输出。为什么？

c++ - 尝试一个问题，但我编写的代码没有给出大量的输出。为什么？

问题描述

我正在尝试这个问题。

13195 的质因数是 5、7、13 和 29。数字 600851475143 的最大质因数是多少？

我写了以下代码：

#include<iostream>
#define num 600851475143
using namespace std;
int isprime(unsigned long long int n)
{
  unsigned long long int c=0;
  for(unsigned long long int i=2;i<n;i++)
  {
      if(n%i==0)
      {
          c++;
          break;
     }
  }
  if(c==0)
  {
      return 1;
  } 
  else
  {
      return 0;
  }
 }
 int main()
 {
 unsigned long long int a,i,n=num;
 while(n-- && n>1)
 {  
     if(isprime(n)==1 && num%n==0)
     {
         cout<<n;
         break;
     }
 }
 return 0;
}

代码出现的问题是它适用于 13195 和其他小值。但是没有得到 600851475143 的任何输出。任何人都可以解释为什么它不能用于大值，并告诉应该在这些中进行的更改以获得正确的输出。

标签： c++c++11math

解决方案

下面的代码片段来自 c（但也应该在 c++ 中运行得很好）：

#include <stdio.h>

#define uIntPrime       unsigned long long int
#define uIntPrimeFormat "llu"

uIntPrime findSmallestPrimeFactor(uIntPrime num)
{
    uIntPrime limit = num / 2 + 1;

    for(uIntPrime i=2; i<limit; i++)
    {
        if((num % i) == 0)
        {
            return i;
        }
    }

    return num;
}

uIntPrime findLargestPrimeFactor(uIntPrime num)
{
    uIntPrime largestPrimeFactor = 1; // start with the smallest possible value

    while (num > 1) {
        uIntPrime primeFactor = findSmallestPrimeFactor(num);
        if (primeFactor > largestPrimeFactor) largestPrimeFactor = primeFactor;
        num = num / primeFactor;
    }

    return largestPrimeFactor;
}

这怎么行？

（第一个功能：）从 2 开始计算数字意味着您从低端的素数开始。（计数时非素数的数字只是不能作为无分数除数，同时它们的素数因子分量已经被探测过，因为它们较低。）

（第二个功能：）如果找到有效因子，则从相关数字中提取该因子。因此，可以重复在抽出的数字中搜索现在最小的素数。（条件可能是多余的，因为无论如何都会首先找到较低的数字 - 但它可能类似于您熟悉的搜索模式 - 就像在最小/最大/其他条件搜索中一样。我现在把它留给你来证明使用您自己的主程序进行测试是对还是错。）停止条件是关于提取最后一个因子意味着将值除以自身并为 num 获得值 1。

（当然还有很大的空间可以加快速度！）

推荐阅读