Eratosthenes의 체를 가진 소수 찾기 (원래 :이 배열을 준비하는 더 좋은 방법이 있습니까?)

StackOverflow https://stackoverflow.com/questions/586284

문제

메모: 아래 버전 2는 Eratosthenes의 체를 사용합니다. 내가 원래 요청한 것에 도움이되는 몇 가지 답변이 있습니다. Eratosthenes 방법의 체를 선택하고 구현하고 질문 제목과 태그를 적절하게 변경했습니다. 도움을 준 모든 분들께 감사드립니다!

소개

나는 지정된 상한보다 적은 소수를 포함하는 int 배열을 생성하는이 멋진 작은 방법을 썼습니다. 매우 잘 작동하지만 우려가 있습니다.

방법

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    int [] primes = new int [index];
    while(--index >= 0) {
        primes [index] = temp [index];
    }
    return primes;
}

내 우려

내 우려는 메소드가 반환 될 최종 요소 수에 비해 너무 큰 배열을 만들고 있다는 것입니다. 문제는 지정된 숫자보다 작은 소수 수를 올바르게 추측하는 좋은 방법을 모른다는 것입니다.

집중하다

이것이 프로그램이 배열을 사용하는 방법입니다. 이것이 제가 개선하고 싶은 것입니다.

  1. 나는 한계보다 모든 숫자를 적게 유지하기에 충분히 큰 임시 배열을 만듭니다.
  2. 나는 소수를 생성하면서 내가 생성 한 수의 수를 유지하면서 소수를 생성합니다.
  3. 나는 소수 만 보유 할 수있는 올바른 차원 인 새로운 배열을 만듭니다.
  4. 각 소수를 거대한 배열에서 올바른 차원의 배열로 복사합니다.
  5. 생성 한 소수 만 고정하는 올바른 치수의 배열을 반환합니다.

질문

  1. 전체 청크 (한 번에)를 복사 할 수 있습니까?temp[] 그것은 0이 아닌 요소가 있습니다 primes[]두 배열을 모두 반복하지 않고 요소를 하나씩 복사하지 않습니까?
  2. 인스턴스화시 차원을 요구하기보다는 요소가 추가 될 때 성장할 수있는 다양한 프리미티브처럼 행동하는 데이터 구조가 있습니까? 프리미티브 배열을 사용하는 것과 비교하여 성능 페널티는 무엇입니까?

버전 2 (감사합니다 존 스키트):

private static int [] generatePrimes(int max) {
    int [] temp = new int [max];
    temp [0] = 2;
    int index = 1;
    int prime = 1;
    boolean isPrime = false;
    while((prime += 2) <= max) {
        isPrime = true;
        for(int i = 0; i < index; i++) {
            if(prime % temp [i] == 0) {
                isPrime = false;
                break;
            }
        }
        if(isPrime) {
            temp [index++] = prime;
        }
    }
    return Arrays.copyOfRange(temp, 0, index);
}

버전 3 (감사합니다 폴 톰린)를 사용합니다 Erastosthenes의 체:

private static int [] generatePrimes(int max) {
    boolean[] isComposite = new boolean[max + 1];
    for (int i = 2; i * i <= max; i++) {
        if (!isComposite [i]) {
            for (int j = i; i * j <= max; j++) {
                isComposite [i*j] = true;
            }
        }
    }
    int numPrimes = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) numPrimes++;
    }
    int [] primes = new int [numPrimes];
    int index = 0;
    for (int i = 2; i <= max; i++) {
        if (!isComposite [i]) primes [index++] = i;
    }
    return primes;
}
도움이 되었습니까?

해결책

배열의 모든 단일 요소를 가능한 모든 요소와 비교하여 프라임을 찾는 방법은 끔찍하게 비효율적입니다. 당신은 a 에라 토스 테네스의 체 전체 배열에서 한 번에. 훨씬 적은 비교를 수행하는 것 외에도 분할보다는 추가를 사용합니다. 부서는 훨씬 느립니다.

다른 팁

ArrayList<> 에라 토스 테네스의 체

// Return primes less than limit
static ArrayList<Integer> generatePrimes(int limit) {
    final int numPrimes = countPrimesUpperBound(limit);
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    boolean [] isComposite    = new boolean [limit];   // all false
    final int sqrtLimit       = (int)Math.sqrt(limit); // floor
    for (int i = 2; i <= sqrtLimit; i++) {
        if (!isComposite [i]) {
            primes.add(i);
            for (int j = i*i; j < limit; j += i) // `j+=i` can overflow
                isComposite [j] = true;
        }
    }
    for (int i = sqrtLimit + 1; i < limit; i++)
        if (!isComposite [i])
            primes.add(i);
    return primes;
}

프라임 수의 상한에 대한 공식은 max (보다 wolfram.com):

static int countPrimesUpperBound(int max) {
    return max > 1 ? (int)(1.25506 * max / Math.log((double)max)) : 0;
}

생성 ArrayList<Integer> 그런 다음 An으로 변환하십시오 int[] 결국.

다양한 제 3자가 있습니다 IntList (등) 수업은 주변에 있지만, 당신이 아니라면 진짜 권투의 히트가 걱정 된 몇 가지 정수에 대해 걱정하면서, 나는 그것에 대해 걱정하지 않을 것입니다.

당신은 사용할 수 있습니다 Arrays.copyOf 그래도 새 배열을 만듭니다. 필요할 때마다 크기가 두 배로 늘어나면서 크기를 조정 한 다음 끝에서 트리밍 할 수도 있습니다. 그것은 기본적으로 그것을 모방 할 것입니다 ArrayList 행동.

에라토스테네스의 체를 사용한 알고

public static List<Integer> findPrimes(int limit) {

    List<Integer> list = new ArrayList<>();

    boolean [] isComposite = new boolean [limit + 1]; // limit + 1 because we won't use '0'th index of the array
    isComposite[1] = true;

    // Mark all composite numbers
    for (int i = 2; i <= limit; i++) {
        if (!isComposite[i]) {
            // 'i' is a prime number
            list.add(i);
            int multiple = 2;
            while (i * multiple <= limit) {
                isComposite [i * multiple] = true;
                multiple++;
            }
        }
    }

    return list;
}

위의 Algo를 묘사 한 이미지 (회색 색상 셀은 소수를 나타냅니다. 모든 숫자를 소수로 간주하기 때문에 전체는 그리드가 처음에는 회색입니다.)

enter image description here

이미지 출처 : Wikimedia

가장 쉬운 해결책은 일부 구성원을 반환하는 것입니다. 수집 프레임 워크 배열 대신.

Java 1.5를 사용하고 있습니까? 돌아 오지 않겠습니까? List<Integer> 그리고 사용 ArrayList<Integer>? 반환 해야하는 경우 int[], 목록을 변환하여 할 수 있습니다 int[] 처리가 끝날 때.

Paul Tomblin이 지적한 것처럼 알고리즘이 더 좋습니다.

그러나 당신이 가진 것을 유지하고 결과 당 객체를 가정하면 너무 큽니다.

당신은 배열에만 추가됩니다. 따라서 비교적 작은 int [] 배열을 사용하십시오. 완전 사용하면 목록에 추가하고 교체품을 만듭니다. 끝에 올바르게 크기가 크기가있는 배열로 복사하십시오.

또는 int [] 배열의 크기를 추측하십시오. 너무 작다면 현재 배열 크기보다 큰 크기의 크기로 int []로 교체하십시오. 이것의 성능 오버 헤드는 크기에 비례합니다. (이것은 최근 StackoverFlow 팟 캐스트에서 간단히 논의되었습니다.)

이제 기본 체를 제자리에 설치 했으므로 내부 루프는 계속해야합니다. temp[i]*temp[i] > prime.

정말 효율적인 구현이 있습니다.

  1. 우리는 짝수 숫자를 유지하지 않으므로 메모리 사용량을 절반으로 줄입니다.
  2. 우리는 사용 BitSet, 숫자 당 하나의 비트 만 필요합니다.
  3. 우리는 간격에서 프라임 수에 대한 상한을 추정하므로 initialCapacity 배열의 경우 적절합니다.
  4. 우리는 루프에서 어떤 종류의 구분도 수행하지 않습니다.

코드는 다음과 같습니다.

public ArrayList<Integer> sieve(int n) {
    int upperBound = (int) (1.25506 * n / Math.log(n));
    ArrayList<Integer> result = new ArrayList<Integer>(upperBound);
    if (n >= 2)
        result.add(2);

    int size = (n - 1) / 2;
    BitSet bs = new BitSet(size);

    int i = 0;
    while (i < size) {
        int p = 3 + 2 * i;
        result.add(p);

        for (int j = i + p; j < size; j += p)
            bs.set(j);

        i = bs.nextClearBit(i + 1);
    }

    return result;
}

코드를 재구성하십시오. 임시 배열을 버리고 대신 정수를 프라임 테스트하는 기능을 작성하십시오. 기본 유형 만 사용하기 때문에 합리적으로 빠릅니다. 예를 들어, 예를 들어, 프라임 인 정수 목록을 루프하고 빌드하기 전에 마침내이를 배열로 변환하여 반환 할 수 있습니다.

나는 마침내 프로그램을 마쳤습니다. 그것은 최적화 된 체입니다.

public static int[] generatePrimes(int max) {
    boolean[] isComposite = new boolean[max + 1];
    LinkedList<Integer> Primes = new LinkedList<>(); //linkedlist so not have to iterate 2 times
    int sqrt = (int) Math.sqrt(max); //end at the square root
    for (int i = 2; i <= sqrt; i++) {
        if (!isComposite[i]) {
            int s = i*i; //start from the prime's square
            while (s <= max) {
                isComposite[s] = true; //oh no its a not prime
                s+=i;
            }
        }
    }
    for(int i = 2; i < max; i++){
        if(!isComposite[i]){
            Primes.add(i);
        }
    }
    int[] result = new int[Primes.size()];
    for (int i = 0; i < result.length; i++) {
        result[i] = Primes.get(i);
    }
    return result;
}

이것이 당신의 상황에 적합할지 확실하지 않지만 내 접근 방식을 볼 수 있습니다. 나는 나의 사용을 사용했다 에라 토스 테네스의 체.

  public static List<Integer> sieves(int n) {
        Map<Integer,Boolean> numbers = new LinkedHashMap<>();

        List<Integer> primes = new ArrayList<>();

        //First generate a list of integers from 2 to 30
        for(int i=2; i<n;i++){
            numbers.put(i,true);
        }

        for(int i : numbers.keySet()){
            /**
             * The first number in the list is 2; cross out every 2nd number in the list after 2 by 
             * counting up from 2 in increments of 2 (these will be all the multiples of 2 in the list):
             * 
             * The next number in the list after 2 is 3; cross out every 3rd number in the list after 3 by 
             * counting up from 3 in increments of 3 (these will be all the multiples of 3 in the list):
             * The next number not yet crossed out in the list after 5 is 7; the next step would be to cross out every
             * 7th number in the list after 7, but they are all already crossed out at this point,
             * as these numbers (14, 21, 28) are also multiples of smaller primes because 7 × 7 is greater than 30. 
             * The numbers not crossed out at this point in the list are all the prime numbers below 30:
             */
            if(numbers.get(i)){
                for(int j = i+i; j<n; j+=i) {
                    numbers.put(j,false);
                }
            }
        }


        for(int i : numbers.keySet()){
            for(int j = i+i; j<n && numbers.get(i); j+=i) {
                numbers.put(j,false);
            }
        }

        for(int i : numbers.keySet()){
           if(numbers.get(i)) {
               primes.add(i);
           }
        }
        return primes;
    }

Wikipedia에 설명 된 각 단계에 대한 의견이 추가되었습니다.

나는 Hashmap을 사용하여 매우 간단하다는 것을 알았습니다. 

import java.util.HashMap;
import java.util.Map;

/*Using Algorithms such as sieve of Eratosthanas */

public class PrimeNumber {

    public static void main(String[] args) {

        int prime = 15;
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();

        hashMap.put(0, 0);
        hashMap.put(1, 0);
        for (int i = 2; i <= prime; i++) {

            hashMap.put(i, 1);// Assuming all numbers are prime
        }

        printPrimeNumberEratoshanas(hashMap, prime);

    }

    private static void printPrimeNumberEratoshanas(HashMap<Integer, Integer> hashMap, int prime) {

        System.out.println("Printing prime numbers upto" + prime + ".....");
        for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
            if (entry.getValue().equals(1)) {
                System.out.println(entry.getKey());
                for (int j = entry.getKey(); j < prime; j++) {
                    for (int k = j; k * j <= prime; k++) {
                        hashMap.put(j * k, 0);
                    }
                }

            }
        }

    }

}

이것이 효과적이라고 생각하십시오

public static void primes(int n) {
        boolean[] lista = new boolean[n+1];
        for (int i=2;i<lista.length;i++) {
            if (lista[i]==false) {
                System.out.print(i + " ");
            }
            for (int j=i+i;j<lista.length;j+=i) {
                lista[j]=true;
            }
        }
    }
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top