Question

我正在努力解决欧勒项目的挑战,在这项挑战中,我需要确定投入数量的最大主要因素。

我尝试了两处 app:

这种方法首先确定小麦的价值是主要价值还是非主要价值。如果价值是主要价值,如果是个因素,则进行核对。所有主子都被推向阵列,阵列的最终价值也得到恢复。

function largestPrimeFactor(number) {

  let arr = [];

  for (let i = 2; i <= number; i++) {

    let flag = 0;

      for (let j = 2; j < i; j++) {

          if (i % j === 0) {
            flag = 1;
            break;
          }
      }

      if (flag === 0) {
        
        if (number % i === 0) {
          arr.push(i);
        }
      }
    }

  return arr[arr.length-1];
}

这种做法首先决定了若干因素。搭乘的通道为每一种价值创造了各种剩余物。如果通过确定所有剩余部分是否为非零数字来检验数据是主要数目的话。

function largestPrimeFactor(number) {

  let arr = [];

  for (let i = 2; i <= number; i++) {

    if (number % i === 0) {

    let num = i;
    let tempArr = [];

        for (let j = num-1; j > 1; j--) {
          tempArr.push(num %j );
        }

      if (tempArr.every(val => val > 0)) {
        arr.push(num)
      }

    }
  }

  let largestPrime = arr[arr.length-1]
  return largestPrime;
}

除了超过6 000 000(60亿)的试验投入外,这两种方法对所有试验投入都适用。确切投入为600851475143。我怎么能够以不同的方式对待这一挑战,以使文字不停。

Answer 1

如果某一数字是首要的,请加以测试。您可使用Miller-Rabin在O(log(n)上解决这一问题,这一条速度要快得多。

而且,如果你想要知道编号n的最大主要因素,那么你就可以利用Sieve来寻找主要数字,并随心所欲,因为N可以是大的,我只想在某个时候加快。

using ll = long long;
const int N = 5000000;
int lpf[N];
vector <int> primes;
void sieve(){
    for(int i=2; i<N; i++){
        if(!lpf[i]){
            lpf[i] = i;
            primes.push_back(i);
            for(ll j=1LL*i*i; j<N; j+=i){
                if(lpf[j] == 0) lpf[j] = i;
            }
        }
    }
}

ll largest_prime_factor(ll n){
    ll prime_factor = 1;
    for(int p: primes){
        if(n < N){
            while(n != 1){
                int d = lpf[n];
                prime_factor = max(prime_factor, (ll)d);
                while(n%d == 0) n /= d;
            }
            break;
        }
        if(n%p == 0){
            prime_factor = max(prime_factor, (ll)p);
            while(n%p == 0) n /= p;
        }
    }
    if(n != 1) prime_factor = max(prime_factor, n);
    return prime_factor;
}

It runs in 36ms on my computer for your question, and should also be instantaneous for multiple queries because half of this time is building the sieve, and for numbers less than N it answers in less than log(n). This should work for numbers up to 2.5e13 and with minor modifications could work up to 64-bit numbers in a similar time.

友情链接