메모리/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

당신은 어떤 언어를 사용하고 있는지 말하지 않으므로이 답변은 일반적인 것입니다.

최대 6,000 개의 소수를 저장하려면 380 바이트 미만인 약 3000 비트 만 필요합니다. 귀하의 기본 솔루션은 에라토스테네스 체 (Sieve of Eratosthenes)와 2가 유일하게 소수라는 사실입니다. 홀수를 처리하도록 체를 설정하면 필요한 저장 공간이 반으로 줄어 듭니다. 체는 각각의 홀수에 대해서만 프라임 (prime) 또는 프라임 (prime)을 보유하지 않기 때문에, 저장은 각 번호에 대해 단일 비트로 감소 될 수 있습니다. 당신이 당신의 체를 설정 한 후에

, 당신은 당신의 범위에서 숫자 체에서 프라임 /하지 프라임 값을 검색 할 필요가, 다른 언어로 지침을 가지고이 일을 포함하여 많은 사이트가 있습니다. 여기에 숫자가 소수 인 경우 확인하기위한 의사 코드는, 체를 가정하는 것은 이미 설정되었습니다

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과 같은 비트 수준 액세스를 허용한다고 가정합니다.