完璧な数字を生成するためのベストC++プログラム

Question

完全な数値を生成する以下のプログラムを作ったが、最初の4つの数値（8128まで）を生成した後、私は長い間待ったが何も起こらなかった。誰もが少なくともlong long intデータ型のオーバーフローまで完璧な数字を生成するプログラムを作る方法を教えてください？

#include<iostream> 
using namespace std; 
void main() { 
    unsigned long long int a = 4, sum = 0; 
    while (true) { 
     for (int i = 1; i <= (a/2); i++) 
     { 
      if (a%i == 0) 
      { 
       sum += i; 
      } 
     } 
     if (sum == a) { cout << a<<" "; a += 2; sum = 0; } 
     else { a += 2; sum = 0; } 
    } 
} 

Answer 1

数字が完璧かどうかを知るには、すべての除数を合計する必要があります。つまり、最初に数字を見つける必要があります。あなたはこれに対して非常にゆっくりしたアプローチを使用しています - 基本的に、候補者の数の半分まで可能なすべての候補者の無理な力です。これには多くの時間がかかり、しばらくすると実行不可能なオプションになります。あなたがチェックしなければならない数字が1'000'000なら、あなたのアプローチは500'000ディビジョンを必要とします。部門は遅いです。あなたはアプローチを変えなければなりません。

各数値が除数であるかどうかを調べるために各数値をテストする必要はありません。これを行うことができます：番号を因数分解し、すべての因子を生成します。

数値を因数分解することは、半分まですべての候補をブルートフォースするよりも信じられないほど速くなる可能性があります。たとえ簡単なアプローチでも、偶数（2を除く）をすべて簡単にスキップすることができ、半分ではなく平方根で停止する必要があります。数が1'000'000の場合は、約500分割、すなわちsqrt（1'000'000）までの奇数が必要です。さらに簡単に改善することができます（素因数の検索を最適化する方法に関する多くの資料があります）。 10年前、「factor.exe」というプログラムが見つかりましたが、今は信頼できるダウンロードを提供することができません（thisまたはthisを見ているかもしれませんが、そこに何があるかを確認していないのであなた自身の責任でダウンロードして実行してください！）、それは1秒未満で60桁の数字を因数分解することができます。 hereは、Javascriptを使用して約0.01秒（平均）で最大20桁の数字を生成するサイトです。これは、数字をいかに早く因数分解することができるかという考え方を与えることに過ぎません。

便利なことにベクトルに格納された素因数を持つと、それらを結合してすべての除数を生成できます。すべての「組み合わせ」は、そのそれぞれについて、それを取るか否かを選択することに対応する。 n（1を除く）の要因がある場合は、2 ⁿの可能性があります。私は指数関数的な成長は良くありませんが、ほとんどの場合、nはlong longに格納できる数値では10を上回る可能性は低いため、限られたセットで作業していることがわかります（これは経験的なことです）。そして繰り返される要因は物事をより速くすることができます（2 は本当に1024の異なる要素につながりません。実際には10個しかありません）。

だから、1'000'000周りの数のために、あなたは簡単で、ほとんどの500の部門とそれを考慮することができ、そしてあなたが10個の素因数を持っている場合は、いくつかの乗算を必要とそれぞれの2 = 1024要因を持つことができます（平均で5）、そして最後にそれらを合計しなければなりません。したがって：500師団、〜5000掛け算、〜1000合計。これはあなたのアプローチで必要とされる500,000区画よりはるかに高速です。

最後に、このアプローチはあなたよりもはるかに高速になる可能性があります。

Answer 2

あなたはsqrt(a)よりも要因が少なく考慮し、それよりも大きい一致度導出することにより因数分解の速度を向上させることができます：それはテストすることができるように、私は機能としてこれを抽出してきた

template<typename T> 
T sum_factors(T n) 
{ 
    T sum = 1; 
    T i = 2; 
    for (; i * i < n; ++i) 
     sum += n%i ? 0 : i + n/i; 
    if (i * i == n) 
     sum += i; 
    return sum; 
} 

を孤立しており、検索ループとは独立して改善されています。

さらに、素因数分解を実行して、各組み合わせの積を合計することもできます（元の数値を戻す「すべての要素」の組み合わせを無視し、1を与える「係数なしの組み合わせ」を忘れないでください）。覚えておいて、候補者を超えた時点でこの合計を計算しないようにすることができます（最大の利益を得るために、最大の条件を最初に得るように合計を注文することをお勧めします）。

次自明のステップは、複数のコアを横切って作業を分割することである。

#include <limits> 
#include <iostream> 

int main() { 
    unsigned long long int a; 
    const auto m = std::numeric_limits<decltype(a)>::max(); 

#pragma omp parallel for 
    for (a = 1; a < m; ++a) { 
     if (sum_factors(a) == a) 
#pragma omp critical 
      std::cout << a << std::endl; 
    } 
    return 0; 
} 

各テストは完全に独立しているので、ここでN、これは、所与の時間に多くの候補としてN回テストします利用可能なプロセッサの数です。 （gcc -fopenmpまたは同等のものを使用してコンパイルしてください）。

---

本当に、しかし、あなたも完全数のEuclid–Euler generatorを使用する場合、および（うまく任意のC++プリミティブ算術型の範囲外）1e1500より下には奇数完全数が存在しないという知識ます。