이 프라임 생성자가 비효율적 인 C ++입니까?

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

  •  04-07-2019
  •  | 
  •  

문제

이것은 효율적인 소수 생성기로 간주됩니다. 이것이 매우 효율적 인 것 같습니다. 프로그램을 느리게 실행하는 스트림 사용입니까?

나는 이것을 제출하려고합니다 Spoj 그리고 그것은 내 시간 제한이 초과되었음을 알려줍니다 ... 

#include <iostream>
#include <sstream>

using namespace std;

int main() {
    int testCases, first, second, counter = 0;
    bool isPrime = true;
    stringstream out;

    cin >> testCases;

    for (int i = 0; i < testCases; i++) {
        // get the next two numbers
        cin >> first >> second;

        if (first%2 == 0)
            first++;

        // find the prime numbers between the two given numbers
        for (int j = first; j <= second; j+=2) {
            // go through and check if j is prime
            for (int k = 2; k < j; k++) {
                if (j%k == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                out << j << "\n";
            }
            isPrime = true;
        }
        out << "\n";
    }

    cout << out.str();

    return 0;
}

편집 : 프로그램은 입력에 지정된 숫자 사이에 소수를 생성해야합니다. 자세한 내용은 여기를 참조하십시오. 주요 생성기 문제 )

-Tomek

도움이 되었습니까?

해결책

이것은 순진한 알고리즘보다 한 단계 (짝수 숫자를 건너 뛰기)입니다. 나는 제안 할 것이다 에라 토스 테네스의 체 보다 효율적인 알고리즘으로. 위의 링크에서 :

알고리즘의 복잡성은 O (n)의 메모리 요구 사항이있는 O ((Nlogn) (loglogn))입니다. 휠 인수 화와 같은 기본 최적화와 함께 Eratosthenes의 체의 세그먼트 버전은 O (N) 작업 및 O (N1 / 2Loglogn / Logn) 비트의 메모리를 사용합니다.

당신이 제공하는 알고리즘은 O (n^2) 근처에 있습니다. Evens를 건너 뛰면 얻는 속도는 첫 번째 테스트에서 고른 숫자가 프라임이 아니기 때문에 그다지 좋지 않습니다. 체는 메모리 요구 사항이 훨씬 높지만 런타임 복잡성은 큰 경우 훨씬 우수합니다. N.

다른 팁

당신은 검색하고 있습니다 많은 당신이해야 할 것보다 더 많은 숫자 - 대부분 당신은 가면됩니다. <= (sqrt(num)).

Eratosthenes의 간단한 체가 있습니다. 큰 부울 배열을 사전 선고 할 필요는 없지만 시간과 공간에서 여전히 >> o (n)입니다. 그러나 메모리가 충분한 한 현재 순진한 방법보다 눈에 띄게 빠르야합니다.

#include <iostream>
#include <map>

using namespace std;

template<typename T = int, typename M = map<T, T> >
class prime_iterator {
    public:
        prime_iterator() : current(2), skips() { skips[4] = 2; }
        T operator*() { return current; }
        prime_iterator &operator++() {
            typename M::iterator i;
            while ((i = skips.find(++current)) != skips.end()) {
                T skip = i->second, next = current + skip;
                skips.erase(i);
                for (typename M::iterator j = skips.find(next);
                        j != skips.end(); j = skips.find(next += skip)) {}
                skips[next] = skip;
            }
            skips[current * current] = current;
            return *this;
        }
    private:
        T current;
        M skips;
};

int main() {
    prime_iterator<int> primes;
    for (; *primes < 1000; ++primes)
        cout << *primes << endl;
    return 0;
}

이것이 당신에게 너무 느리면, 당신은 Atkin의 체, 에라 토스 텐의 최적화 된 체.

실제로, 이들은 생성 할 프라임 범위가 낮게 시작되는 경우에만 비교적 효율적입니다. 하한이 이미 상당히 크고 상한이 하단보다 크지 않다면 체질 방법이 낭비되는 작업이며 원시 테스트.

그리고 한 가지 더, 루프에서 sqrt (n)를 사용하지 마십시오.

for(int k=1;k<sqrt(n);++k)

좋은 최적화가 없으면 모든 반복에서 SQRT가 계산됩니다.

사용

for (int k=1;k*k < n;++k)

또는 간단히

int sq = sqrt ( n );
for (int k=1;k<sq;++k)

약간 더 효율적으로 만들 수 있습니다. K를 2시에 시작할 필요가 없으며 이미 짝수를 테스트하지 않아도됩니다. 따라서 3시에 K를 시작하십시오.
그런 다음 다른 짝수 숫자를 테스트 할 필요가 없기 때문에 매번 K를 2로 증가시킵니다. 내가 생각할 수있는 가장 효율적인 방법은 숫자가 알려진 소수로 나눌 수 있는지 만 테스트하는 것입니다 (그런 다음 다른 것을 찾을 때 테스트 목록에 추가 할 때).

for (int k = 2; k < j; k++) {
     if (j%k == 0) {
         isPrime = false;
         break;
     }
}

해야한다:

for(int k = 3; k <= j/2; k+=2 )
{
  if( j % k == 0 )
      break;
}

J/2는 실제로 SQRT (J) 여야하지만 일반적으로 충분한 추정입니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top