Cコードは永遠に実行し続けます*

Question

Cで巨大な数値の最大の素因数を見つけようとしていますが、100や10000のような小さな数値に対してはうまく動作しますが失敗します。私のcore2duoとi5）の数十分間、非常に大きいtargetの番号（対象番号のコードを参照してください） アルゴリズムは正しいですか？

私はCの新人であり、大きな数字で本当に苦労しています。私が欲しいのは、訂正やガイダンスは解決策ではありません。私はbignumバインディングやものでpythonを使ってこれを行うことができます（私はまだ試していませんが、確かにです）。あるいは、私はいくつかの小さな間違いをしているかもしれません実現するにはあまりにも疲れて、とにかくここに私が書いたコードです：

#include <stdio.h> 
// To find largest prime factor of target 
int is_prime(unsigned long long int num); 

long int main(void) { 
    unsigned long long int target = 600851475143; 
    unsigned long long int current_factor = 1; 
    register unsigned long long int i = 2; 
    while (i < target) { 
     if ((target % i) == 0 && is_prime(i) && (i > current_factor)) { //verify i as a prime factor and greater than last factor 
      current_factor = i; 
     } 
     i++; 
    } 
    printf("The greates is: %llu \n",current_factor); 
return(0); 
} 


int is_prime (unsigned long long int num) { //if num is prime 1 else 0 
    unsigned long long int z = 2; 
    while (num > z && z !=num) { 
     if ((num % z) == 0) {return 0;} 
     z++; 
    } 

return 1; 
} 

Answer 1

6000億回の繰り返しは、ほんのわずかな時間がかかります。これを実質的に減らす必要があります。

ヒント：任意の整数値xが与えられた場合、yが要因であることが判明した場合、x/yも要因であることが暗黙的に検出されています。つまり、要素は常にペアになります。したがって、冗長な作業を行う前にどのくらい反復する必要があるかには限界があります。

この制限は何ですか？さて、yがx/yより大きくなるクロスオーバーポイントは何ですか？

この最適化を外側ループに適用すると、コードのランタイムはis_prime関数によって制限されることがわかります。もちろん、同様の手法を適用することもできます。

Answer 2

の数の平方根になるまで反復することにより、我々はそれの要因のすべてを取得することができます（factorとN/factorとfactor<=sqrt(N)）。この小さなアイデアのもとで、解決策が存在します。我々がチェックするsqrt(N)よりも小さい因子は、対応する因子がsqrt(N)より大きい。だから、sqrt(N)までチェックするだけで、残りの要素を得ることができます。

ここでは、プライム検索アルゴリズムを明示的に使用する必要はありません。因数分解ロジック自体は、ターゲットが素数であるかどうかを推論します。したがって、ペアワイズ要因を確認するだけです。

unsigned long long ans ; 
for(unsigned long long i = 2; i<=target/i; i++) 
    while(target % i == 0){ 
     ans = i; 
     target/=i; 
    } 

if(target > 1) ans = target; // that means target is a prime. 
//print ans 

^{編集：追加する点（chux） - 以前のコードでi*iは、我々はi<=target/iを使用する場合、回避することができるオーバーフローにつながる可能性があります。整数演算とダブル数学の混合が丸め誤差を起こしやすい -}

^{また別の選択肢がここ}

unsigned long long sqaure_root = isqrt(target); 
for(unsigned long long i = 2; i<=square_root; i++){ 
... 
} 

を持っているだろうが以来sqrtの使用は賢明な選択ではないよりも注意してください。

答えが6857の場合、ターゲットに与えられます。

Answer 3

is_primeは、numを他の素数に対してのみテストする必要があるという点で、鶏と卵の問題があります。したがって、それは3の倍数であるため、チェックする必要はありません。

is_primeは素数の配列を維持することができ、新しいnumがテストされるたびにそれが配列に追加されます。 num isrは配列の各素数に対してテストされ、配列内のいずれかの素数で割り切れない場合は、それ自身が素数であり、配列に追加されます。あなたがターゲットとする素数の数を計算する形式がない限り、arayはmallocされ、rellocされなければなりません（私はそのような公式は存在しないと信じています）。

EDIT：ターゲット600,851,475,143をテストするための素数の数は約7,500,000,000になり、テーブルがメモリ不足になる可能性があります。

次のようなアプローチを適合させることができる。

• 上にブルートフォースを使用すること

• 上方素数ためunsigned long long intを使用するUINT_max

• の素数までunsiged intを使用します特定のメモリ消費。

UINT_MAX 4,294,967,295として定義され、周りの千億まで素数をカバーする7.5 * 4 = 30GB

を要するであろうもThe Prime Pagesを参照してください。

Answer 4

何もそれだけで例えば、最適化を必要とする、間違ったではありません：（Z < NUM）ながら

int is_prime(unsigned long long int num) { 
    if (num == 2) { 
     return (1);    /* Special case */ 
    } 
    if (num % 2 == 0 || num <= 1) { 
     return (0); 
    } 
    unsigned long long int z = 3; /* We skipped the all even numbers */ 
    while (z < num) {    /* Do a single test instead of your redundant ones */ 
     if ((num % z) == 0) { 
      return 0; 
     } 
     z += 2;      /* Here we go twice as fast */ 
    } 
return 1; 
} 

も大きな他の問題があるが、あなたが解決策を望んでいないので、私はあなたがどのように見つけてみましょうそれを最適化し、同様に最初の関数を自分自身で調べます。

EDIT：私の前に50秒前に投稿された素数配列のリストが最高ですが、初心者で操作が簡単ではないので、簡単なソリューションを提供することにしました。ポインターやものを学ぶ）。

Answer 5

コードは、2つの主要な問題

1. while (i < target)ループは非常に非効率的であるがあります。因数を見つけると、targetをtarget = target/i;に減らすことができました。さらに、因子iが複数回現れる可能性がある。修正は表示されません。

2. is_prime(n)は非常に非効率的です。そのwhile (num > z && z !=num)はループすることができますn時間。ここでも、商を使用して反復をsqrt(n)回に制限します。

   int is_prime (unsigned long long int num) { 
       unsigned long long int z = 2; 
       while (z <= num/z) { 
       if ((num % z) == 0) return 0; 
       z++; 
       } 
       return num > 1; 
   }