メモリ/ CPUの最適化？

Question

私のプログラムは多くのメモリと処理能力を使用していますが、最大6000までしか検索できません。このメモリ使用量を減らす方法はありますか？これは、メモリをスマートに扱う方法を知っていることがうれしいので、将来のプログラミングに役立ちます。

ArrayList<Integer> factor = new ArrayList<Integer>(); 
    ArrayList<Integer> non = new ArrayList<Integer>(); 
    ArrayList<Integer> prime = new ArrayList<Integer>(); 

    Scanner sc = new Scanner(System.in); 
    System.out.println("Please enter how high we want to search"); 
    long startTime = System.nanoTime(); 
    int max = sc.nextInt(); 
    int number = 2; 

while (number < max) 
{ 

     for (int i=0;i<prime.size();i++) 
    { 
      int value = prime.get(i); 
      if (number % value == 0) 
     { 
      factor.add(value); 
     } 
     else 
     { 
      non.add(value); 
     } 
    } 

    if(factor.isEmpty()) 
    { 
     prime.add(number); 
    } 
    else 
    { 
     composite.add(number);   
    } 
    factor.clear(); 
    number++; 


} 
    int howMany=prime.size(); 
    System.out.printf("The are "+howMany+" prime numbers up to " +max + " and they are: " +prime); 
    System.out.println(); 

} 

Answer 1

どの言語を使用しているのかわからないので、この回答は一般的です。

6000までの素数を保存するには、380バイト未満の約3000ビットしか必要ありません。あなたの基本的な解決策は、Eratosthenesのふるいと2だけが唯一の素数であるという事実です。奇数のみを処理するようにふるいを設定すると、必要なストレージが半分になります。篩は各奇数に対してプライムしか保持しないかプライムを保持しないので、記憶は各数に対して1ビットに減らすことができる。

ふるいを設定したら、さまざまな言語の指示があるサイトが多数ありますが、範囲内の数字のふるいからプライム/非プライム値を取得するだけで済みます。

boolean function isPrime(number) 

    // Low numbers 
    if (number < 2) 
    return false 
    endif 

    // Even numbers 
    if (number is even) 
    return number == 2 
    endif 

    // Odd numbers >= 3 
    return sieve[(number - 1)/2] == 1 

end function 

低い数字が素数でない、次のとおりです。ここ数はふるいがすでに設定されていると仮定すると、素数であるかどうかをチェックするための擬似コードです。 2だけが偶数である。他のすべての偶数はプライムではありません。奇数2n + 1の素数フラグは、篩内のビットnに格納されます。これは、あなたが使用している言語がJavaでBitSetのようなビットレベルのアクセスを許可していることを前提としています。