ふるい - 素因数

Question

私はいくつかの自然数の最大の素因数を見つけるためにふるいを利用するには、以下の2より大きい

プログラムのビルドと実行し、小さなテスト値のために働く書いたが、単に

私はこれを書いていますが、おそらく非常に効率が悪いと思います。ふるいが何であるかを見つけた後です。

改善をお勧めしますか？

ありがとうございます。

//LARGEST PRIME FACTOR w/SIEVE OF ERATHOSTHENES 
#include <iostream> 
#include <math.h> 

using namespace std; 

unsigned long long int numberToCheck=0; 

void sieve(unsigned long long int checkNumber) 
{ 
    checkNumber=numberToCheck; 
    unsigned long long int root=(int)(sqrt(checkNumber)); 
    unsigned long long int primeFlagger[checkNumber+1]; 

    for(unsigned long long int i=0;i<=checkNumber;i++) 
    { 
     primeFlagger[i]=1; 
    } 

    primeFlagger[0]=0; 
    primeFlagger[1]=0; 

    for(unsigned long long int j=2;j<=checkNumber;j++) 
    { 
     if(primeFlagger[j]==1) 
     { 
      for(unsigned long long int k=2;(k*j)<=checkNumber;k++) 
      { 
       primeFlagger[j*k]=0; 
      } 
     } 
    } 

    for(unsigned long long int l=checkNumber;l>=0;l--) 
    { 
     if(primeFlagger[l]==1) 
     { 
      if(checkNumber%l==0) 
      { 
       cout<<l<<" is the largest prime factor"<<endl; 
       break; 
      } 
     } 
    } 
} 

int main() 
{ 
    cout<<"Largest prime factor less then or equal to? "<<endl; 
    cin>>numberToCheck; 
    cout<<endl; 
    cout<<"Retrieving largest prime factor..."<<endl; 

    sieve(numberToCheck); 



    return 0; 
} 

Answer 1

あなたの配列unsigned long long int primeFlagger[checkNumber+1];内部sieve funcが長すぎます。関数または動的メモリ割り当ての範囲外で、グローバルスコープ内で配列を使用します。

また、unsigned long longは必要ありません。その最大の整数型のデータ型で、その1ビットのみを使用します。タイプをブールに変更すると、あなたも役に立ちます。

他の問題があります：

• unsigned long long int root=(int)(sqrt(checkNumber)); - 数が本当に多い場合は、sqrt(checkNumber)はintをオーバーフローすることができます。
• unsigned long long int primeFlagger[checkNumber+1]; - タイプcheckNumberは、おそらくstd::size_tより大きく、配列インデックスの型と割り当て可能な最大メモリ領域の型です。 unsigned long longの配列サイズを作ることはできません。
• checkNumber=numberToCheck; - これは必要ありません。 numberToCheckはすでにパラメータcheckNumberとして機能しています。内側のsieveは、numberToCheckと等しくなります。
• for(unsigned long long int j=2;j<=checkNumber;j++) - このループは終了する必要があります。j<=root。これは、非原始数をすべてマークするのに十分です。

実際にこのような大きな数値で作業する必要がある場合は、segmented sieveを使用してください。