이 프라임 생성자가 비효율적 인 C ++입니까?
-
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) 여야하지만 일반적으로 충분한 추정입니다.