如何在C中找到完美的數字10^18？

Question

我有一個C代碼關閉下面發現大量完美的數字，

#include <stdio.h> 

int main() 
{ 
    unsigned long long num,i,sum; 

    while (scanf ("%llu",&num) != EOF && num) 
    { 
     sum = 1; 

     for (i=2; i*i<=num; i++) 
     { 
      if (num % i == 0) 
      { 
       if (i*i == num) 
        sum += i; 
       else 
        sum += (i + num/i); 
      } 
     } 

     if (sum == num) 
      printf ("Perfect\n"); 
     else if (sum > num) 
      printf ("Abundant\n"); 
     else 
      printf ("Deficient\n"); 
    } 

    return 0; 
} 

我試圖找到一個數是否是完美的，豐富或不足。我運行一個循環直到num的平方根以減少運行時間。它工作正常<= 10^15，但對於較大的值，執行所需的時間太長。

例如，對於以下的輸入集，

8 
6 
18 
1000000 
1000000000000000 
0 

這個代碼顯示的以下輸出

Deficient 
Perfect 
Abundant 
Abundant 
Abundant 

但是，對於10^16不會迅速作出反應。

那麼，有沒有更好的方法來找到一個值太長的完美數字？或者有沒有更好的算法來實現這裏？ :)

Answer 1

是的，有一個更好的算法。

你的算法基本上是簡單的 - 將一個數字的除數相加，以找到...數字的除數之和（不包括它本身）。但是，你可以使用數論公式來找出一個數字（包括它自己）的除數之和。如果素數除以n是p1，p2，...，pk和那些素數在n規範分解權力a1，a2，...，ak，那麼的n約數的總和

(p1**(a1+1) - 1)/(p1 - 1) * (p2**(a2+1) - 1)/(p2 - 1) * ... 
    * (pk**(ak+1) - 1)/(pk - 1) 

可以比找的n所有除數更快速的找到素因子和它們的指數。從上面的表達式中減去n，就可以得到你想要的總和。

當然，還有一些技巧可以更有效地找到pi和ai：我會把它留給你。

---

順便說一句，如果你的目的只是爲了找到完美的數字，因爲在您的標題，你會做的更好使用Euclid's formula for even prime numbers。通過檢查所有2**p-1的素數p來查找梅森素數，看他們是否是素數 - 也有做這個的捷徑 - 然後用梅森素數構造一個完美數字。但是，這將排除任何odd perfect numbers。如果你找到了，讓數學界知道 - 這會讓你聞名世界。

當然，所有找到完美數字的最快方法是使用其中一些的最佳方式the lists already made。

Answer 2

這是一個數字因式分解的問題。你可以在這裏閱讀更多信息：https://en.wikipedia.org/wiki/Integer_factorization

不幸的是沒有好消息給你 - 數字越大，需要的時間越長。

要開始您的代碼，請儘量不要在每次迭代時乘以i*i。 代替： 爲（ⅰ= 2; I * I < = NUM​​;我++）

計算NUM的平方根首先，然後比較 i <= square_root_of_num in the loop。

Answer 3

// Program to determine whether perfect or not 

# include <bits/stdc++.h> 
using namespace std; 

map<long long int, int> mp; // to store prime factors and there frequency 

void primeFactors(long long int n) 
{ 
// counting the number of 2s that divide n 
while (n%2 == 0) 
{ 
    mp[2] = mp[2]+1; 
    n = n/2; 
} 

long long int root = sqrt(n); 
// n must be odd at this point. So we can skip every even numbers next 
for (long long int i = 3; i <= root; i = i+2) 
{ 
    // While i divides n, count frequency of i prime factor and divide n 
    while (n%i == 0) 
    { 
     mp[i] = mp[i]+1; 
     n = n/i; 
    } 
} 

// This condition is to handle the case whien n is a prime number 
    // greater than 2 
    if (n > 2) 
    { 
     mp[n] = mp[n]+1; 
    } 
} 

long long int pow(long long int base, long long int exp) 
{ 
    long long int result = 1; 
    base = base; 
    while (exp>0) 
    { 
     if (exp & 1) 
      result = (result*base); 
     exp >>= 1; 
     base = (base*base); 
    } 
    return result; 
} 

int main() 
{ 
    long long num, p, a, sum; 

    while (scanf ("%lld",&num) != EOF && num) 
    { 
     primeFactors(num); 
     sum = 1; 

     map<long long int, int> :: iterator i; 
     for(i=mp.begin(); i!=mp.end(); i++) 
     { 
      p = i->first; 
      a = i->second; 
      sum = sum*((pow(p,a+1)-1)/(p-1)); 
     } 

     if (sum == 2*num) 
      printf ("Perfect\n"); 
     else if (sum > num) 
      printf ("Abundant\n"); 
     else 
      printf ("Deficient\n"); 

     mp.clear(); 
    } 

    return 0; 
}