소수 N이 주어지면 다음 소수를 계산할까요?
동료가 C # Dictionary 컬렉션이 해싱과 관련된 난해한 이유로 소수에 따라 크기가 조정된다고 말했습니다. 그리고 저의 즉각적인 질문은 "다음 소수가 무엇인지 어떻게 알 수 있습니까? 거대한 테이블을 이야기합니까 아니면 즉석에서 계산합니까? 이것은 크기 조정을 일으키는 삽입에 대한 무서운 비 결정적 런타임입니다."
그래서 내 질문은 소수 인 N이 주어지면 다음 소수를 계산하는 가장 효율적인 방법은 무엇입니까?
연속 된 소수 사이 의 간격은 매우 작은 것으로 알려져 있으며 소수 370261에 대해 100 개 이상의 첫 번째 간격이 발생합니다. 즉, 대부분의 상황에서 단순한 무차별 대입으로도 충분히 빠르며 O (ln (p) *를 사용합니다. sqrt (p)) 평균입니다.
p = 10,000의 경우 O (921) 작업입니다. O (ln (p)) 삽입 (대략적으로 말하면)마다이 작업을 수행 할 것이라는 점을 염두에두고, 이는 대부분의 최신 하드웨어에서 1 밀리 초 정도 걸리는 대부분의 문제의 제약 범위 내에 있습니다.
약 1 년 전에 저는 C ++ 11 용 비 순차 (해시) 컨테이너를 구현하는 동안 libc ++ 용으로이 영역을 작업했습니다 . 여기에서 내 경험을 공유하겠다고 생각했습니다. 이 경험은 " 무력한 힘" 에 대한 합리적인 정의에 대한 Marcog의 대답 을 뒷받침합니다 .
즉, 단순한 무차별 대입 공격도 대부분의 상황에서 충분히 빠르며 평균적으로 O (ln (p) * sqrt (p))를 사용합니다.
size_t next_prime(size_t n)이 기능의 사양이 어디에 있는지에 대한 여러 구현을 개발했습니다 .
반환 값 : 보다 크거나 같은 가장 작은 소수
n.
의 각 구현 next_prime에는 도우미 함수가 수반됩니다 is_prime. is_prime개인 구현 세부 사항으로 간주되어야합니다. 클라이언트가 직접 호출 할 수 없습니다. 이러한 각 구현은 물론 정확성을 테스트했지만 다음 성능 테스트를 통해 테스트했습니다.
int main()
{
typedef std::chrono::high_resolution_clock Clock;
typedef std::chrono::duration<double, std::milli> ms;
Clock::time_point t0 = Clock::now();
std::size_t n = 100000000;
std::size_t e = 100000;
for (std::size_t i = 0; i < e; ++i)
n = next_prime(n+1);
Clock::time_point t1 = Clock::now();
std::cout << e/ms(t1-t0).count() << " primes/millisecond\n";
return n;
}
나는 이것이 성능 테스트이며 일반적인 사용법을 반영하지 않는다는 점을 강조해야합니다.
// Overflow checking not shown for clarity purposes
n = next_prime(2*n + 1);
모든 성능 테스트는 다음으로 컴파일되었습니다.
clang++ -stdlib=libc++ -O3 main.cpp
구현 1
7 가지 구현이 있습니다. 첫 번째 구현을 표시하는 목적은 x요인에 대한 후보 소수 테스트를 중단하지 못하면 sqrt(x)무차별 대입으로 분류 될 수있는 구현도 달성하지 못했음을 보여주기위한 것입니다. 이 구현은 매우 느립니다 .
bool
is_prime(std::size_t x)
{
if (x < 2)
return false;
for (std::size_t i = 2; i < x; ++i)
{
if (x % i == 0)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
for (; !is_prime(x); ++x)
;
return x;
}
이 구현 e에서는 합리적인 실행 시간을 얻기 위해 100000 대신 100 으로 설정 해야했습니다.
0.0015282 primes/millisecond
구현 2
이 구현은 무차별 대입 구현 중 가장 느리고 구현 1과의 유일한 차이점은 요소가 초과하면 소수 테스트를 중지한다는 것 sqrt(x)입니다.
bool
is_prime(std::size_t x)
{
if (x < 2)
return false;
for (std::size_t i = 2; true; ++i)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x % i == 0)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
for (; !is_prime(x); ++x)
;
return x;
}
참고 sqrt(x)직접 계산하지만,에 의해 추론되지 않는다 q < i. 이렇게하면 수천 배나 빨라집니다.
5.98576 primes/millisecond
marcog의 예측을 검증합니다.
... 이는 대부분의 최신 하드웨어에서 1 밀리 초 정도 걸리는 대부분의 문제의 제약 범위 내에 있습니다.
구현 3
%운영자의 사용을 피함으로써 (적어도 내가 사용하는 하드웨어에서) 속도를 거의 두 배로 높일 수 있습니다 .
bool
is_prime(std::size_t x)
{
if (x < 2)
return false;
for (std::size_t i = 2; true; ++i)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
for (; !is_prime(x); ++x)
;
return x;
}
11.0512 primes/millisecond
구현 4
지금까지 나는 2가 유일한 짝수 소수라는 상식도 사용하지 않았습니다. 이 구현은 이러한 지식을 통합하여 속도를 거의 두 배로 높입니다.
bool
is_prime(std::size_t x)
{
for (std::size_t i = 3; true; i += 2)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
if (x <= 2)
return 2;
if (!(x & 1))
++x;
for (; !is_prime(x); x += 2)
;
return x;
}
21.9846 primes/millisecond
구현 4는 아마도 대부분의 사람들이 "무력한 힘"을 생각할 때 염두에 두는 것입니다.
구현 5
다음 공식을 사용하면 2 나 3으로 나눌 수없는 모든 숫자를 쉽게 선택할 수 있습니다.
6 * k + {1, 5}
여기서 k> = 1. 다음 구현은이 공식을 사용하지만 귀여운 xor 트릭으로 구현되었습니다.
bool
is_prime(std::size_t x)
{
std::size_t o = 4;
for (std::size_t i = 5; true; i += o)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
o ^= 6;
}
return true;
}
std::size_t
next_prime(std::size_t x)
{
switch (x)
{
case 0:
case 1:
case 2:
return 2;
case 3:
return 3;
case 4:
case 5:
return 5;
}
std::size_t k = x / 6;
std::size_t i = x - 6 * k;
std::size_t o = i < 2 ? 1 : 5;
x = 6 * k + o;
for (i = (3 + o) / 2; !is_prime(x); x += i)
i ^= 6;
return x;
}
이는 알고리즘이 숫자의 1/2 대신 소수의 1/3 만 정수로 확인해야 함을 의미하며 성능 테스트에서는 예상 속도가 거의 50 % 증가한 것으로 나타났습니다.
32.6167 primes/millisecond
구현 6
이 구현은 구현 5의 논리적 확장입니다. 다음 공식을 사용하여 2, 3 및 5로 나눌 수없는 모든 숫자를 계산합니다.
30 * k + {1, 7, 11, 13, 17, 19, 23, 29}
또한 is_prime 내의 내부 루프를 펼치고 30 미만의 숫자를 처리하는 데 유용한 "작은 소수"목록을 생성합니다.
static const std::size_t small_primes[] =
{
2,
3,
5,
7,
11,
13,
17,
19,
23,
29
};
static const std::size_t indices[] =
{
1,
7,
11,
13,
17,
19,
23,
29
};
bool
is_prime(std::size_t x)
{
const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
for (std::size_t i = 3; i < N; ++i)
{
const std::size_t p = small_primes[i];
const std::size_t q = x / p;
if (q < p)
return true;
if (x == q * p)
return false;
}
for (std::size_t i = 31; true;)
{
std::size_t q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 6;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 4;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 2;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 4;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 2;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 4;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 6;
q = x / i;
if (q < i)
return true;
if (x == q * i)
return false;
i += 2;
}
return true;
}
std::size_t
next_prime(std::size_t n)
{
const size_t L = 30;
const size_t N = sizeof(small_primes) / sizeof(small_primes[0]);
// If n is small enough, search in small_primes
if (n <= small_primes[N-1])
return *std::lower_bound(small_primes, small_primes + N, n);
// Else n > largest small_primes
// Start searching list of potential primes: L * k0 + indices[in]
const size_t M = sizeof(indices) / sizeof(indices[0]);
// Select first potential prime >= n
// Known a-priori n >= L
size_t k0 = n / L;
size_t in = std::lower_bound(indices, indices + M, n - k0 * L) - indices;
n = L * k0 + indices[in];
while (!is_prime(n))
{
if (++in == M)
{
++k0;
in = 0;
}
n = L * k0 + indices[in];
}
return n;
}
이것은 "무력한 힘"을 넘어서서 속도를 27.5 % 더 높이는 데 좋습니다.
41.6026 primes/millisecond
구현 7
위의 게임을 한 번 더 반복하여 2, 3, 5 및 7로 나눌 수없는 수식을 개발하는 것이 실용적입니다.
210 * k + {1, 11, ...},
소스 코드는 여기에 표시되어 있지 않지만 구현 6과 매우 유사합니다. 이것은 실제로 정렬되지 않은 libc ++ 컨테이너에 사용하기로 선택한 구현 이며 해당 소스 코드는 오픈 소스입니다 (링크에서 찾을 수 있음).
이 마지막 반복은 다음과 같은 추가 14.6 % 속도 향상에 좋습니다.
47.685 primes/millisecond
이 알고리즘을 사용하면 libc ++ 의 해시 테이블 클라이언트 가 자신의 상황에 가장 유리하다고 판단한 소수를 선택할 수 있으며이 응용 프로그램의 성능은 상당히 만족 스럽습니다.
누군가가 궁금한 경우를 대비하여 :
리플렉터를 사용하여 .Net은 현재 크기의 두 배 이상인 가장 작은 소수를 스캔하고 계산하는 것보다 큰 크기에 대해 최대 7199369 범위의 ~ 72 소수의 하드 코딩 된 목록을 포함하는 정적 클래스를 사용한다고 결정했습니다. 잠재적 인 수의 sqrt까지 모든 홀수를 시도 분할하여 다음 소수. 이 클래스는 불변하고 스레드로부터 안전합니다 (즉, 더 큰 소수는 나중에 사용하기 위해 저장되지 않습니다).
좋은 비결은 부분 체를 사용하는 것입니다. 예를 들어, N = 2534536543556 다음에 오는 다음 소수는 무엇입니까?
작은 소수 목록과 관련하여 N의 계수를 확인하십시오. 그러므로...
mod(2534536543556,[3 5 7 11 13 17 19 23 29 31 37])
ans =
2 1 3 6 4 1 3 4 22 16 25
우리는 N 다음에 오는 다음 소수가 홀수 여야한다는 것을 알고 있으며,이 작은 소수 목록의 모든 홀수 배수를 즉시 버릴 수 있습니다. 이러한 계수를 통해 우리는 작은 소수의 배수를 걸러 낼 수 있습니다. 200까지의 작은 소수를 사용한다면 작은 목록을 제외하고 N보다 큰 잠재적 소수를 즉시 버릴 수 있습니다.
보다 명시 적으로 2534536543556 이상의 소수를 찾는 경우 2로 나눌 수 없으므로 해당 값을 초과하는 홀수 만 고려하면됩니다. 위의 계수는 2534536543556이 2 mod 3과 합동이므로 2534536543556 + 1은 0 mod 3과 합동이며 2534536543556 + 7, 2534536543556 + 13 등이어야합니다. 효과적으로, 우리는 필요없이 많은 숫자를 체질 할 수 있습니다. 시험 분할없이 원시성을 테스트합니다.
마찬가지로 사실
mod(2534536543556,7) = 3
2534536543556 + 4는 0 mod 7과 합동임을 알려줍니다. 물론 그 숫자는 짝수이므로 무시해도됩니다. 그러나 2534536543556 + 11은 2534536543556 + 25 등과 같이 7로 나눌 수있는 홀수입니다. 다시 말하지만, 우리는이 숫자를 명확하게 합성 (7으로 나눌 수 있기 때문에)하고 소수가 아닌 것으로 제외 할 수 있습니다.
37까지의 작은 소수 목록 만 사용하여 시작점 2534536543556 바로 다음에 오는 대부분의 숫자를 제외 할 수 있습니다.
{2534536543573 , 2534536543579 , 2534536543597}
그 숫자 중 소수입니까?
2534536543573 = 1430239 * 1772107
2534536543579 = 99833 * 25387763
나는 목록에서 처음 두 숫자의 소인수 분해를 제공하기 위해 노력했습니다. 복합적이지만 소인수가 크다는 것을 확인하십시오. 물론 이것은 우리가 이미 남은 숫자가 작은 소인수를 가질 수 없음을 확인했기 때문에 의미가 있습니다. 짧은 목록의 세 번째 항목 (2534536543597)은 사실 N을 넘어서는 첫 번째 소수입니다. 제가 설명한 체질 체계는 소수이거나 일반적으로 큰 소수 요소로 구성된 수를 생성하는 경향이 있습니다. 그래서 우리는 다음 소수를 찾기 전에 소수의 숫자에만 명시적인 소수성 테스트를 실제로 적용해야했습니다.
유사한 체계는 N = 1000000000000000000000000000을 초과하는 다음 소수를 1000000000000000000000000103으로 빠르게 산출합니다.
프라임 간 거리에 대한 몇 가지 실험입니다.
이것은 다른 답변을 시각화하기위한 보완입니다.
나는 100.000 번째 (= 1,299,709)에서 200.000 번째 (= 2,750,159)까지 소수를 얻었습니다.
일부 데이터 :
Maximum interprime distance = 148
Mean interprime distance = 15
Interprime 거리 주파수 플롯 :
Interprime 거리 대 소수
그냥 "무작위"입니다. 그러나 ...
다음 소수를 계산하는 함수 f (n)은 없습니다. 대신 소수에 대해 숫자를 테스트해야합니다.
n 번째 소수를 찾을 때 1 번째부터 (n-1) 번째까지의 모든 소수를 이미 아는 것도 매우 유용합니다. 왜냐하면 그것들은 인자로 테스트해야하는 유일한 숫자이기 때문입니다.
이러한 이유 때문에 미리 계산 된 큰 소수 집합이 있다고해도 놀라지 않을 것입니다. 특정 소수를 반복적으로 재 계산해야하는 경우에는 실제로 이해가되지 않습니다.
As others have already noted, a means of finding the next prime number given the current prime has not been found yet. Therefore most algorithms focus more on using a fast means of checking primality since you have to check n/2 of the numbers between your known prime and the next one.
Depending upon the application, you can also get away with just hard-coding a look-up table, as noted by Paul Wheeler.
For sheer novelty, there’s always this approach:
#!/usr/bin/perl
for $p ( 2 .. 200 ) {
next if (1x$p) =~ /^(11+)\1+$/;
for ($n=1x(1+$p); $n =~ /^(11+)\1+$/; $n.=1) { }
printf "next prime after %d is %d\n", $p, length($n);
}
which of course produces
next prime after 2 is 3
next prime after 3 is 5
next prime after 5 is 7
next prime after 7 is 11
next prime after 11 is 13
next prime after 13 is 17
next prime after 17 is 19
next prime after 19 is 23
next prime after 23 is 29
next prime after 29 is 31
next prime after 31 is 37
next prime after 37 is 41
next prime after 41 is 43
next prime after 43 is 47
next prime after 47 is 53
next prime after 53 is 59
next prime after 59 is 61
next prime after 61 is 67
next prime after 67 is 71
next prime after 71 is 73
next prime after 73 is 79
next prime after 79 is 83
next prime after 83 is 89
next prime after 89 is 97
next prime after 97 is 101
next prime after 101 is 103
next prime after 103 is 107
next prime after 107 is 109
next prime after 109 is 113
next prime after 113 is 127
next prime after 127 is 131
next prime after 131 is 137
next prime after 137 is 139
next prime after 139 is 149
next prime after 149 is 151
next prime after 151 is 157
next prime after 157 is 163
next prime after 163 is 167
next prime after 167 is 173
next prime after 173 is 179
next prime after 179 is 181
next prime after 181 is 191
next prime after 191 is 193
next prime after 193 is 197
next prime after 197 is 199
next prime after 199 is 211
All fun and games aside, it is well known that the optimal hash table size is rigorously provably a prime number of the form 4N−1. So just finding the next prime is insufficient. You have to do the other check, too.
내가 기억하는 한, 그것은 현재 크기의 두 배 옆에 소수를 사용합니다. 소수를 계산하지 않습니다. 미리로드 된 숫자가 큰 값 (정확히 약 10,000,000 정도는 아님)까지있는 테이블이 있습니다. 해당 숫자에 도달하면 다음 숫자 (예 : curNum = curNum + 1)를 얻기 위해 순진한 알고리즘을 사용하고 다음 방법을 사용하여 유효성을 검사합니다. http://en.wikipedia.org/wiki/Prime_number#Verifying_primality
참고 URL : https://stackoverflow.com/questions/4475996/given-prime-number-n-compute-the-next-prime
'IT Share you' 카테고리의 다른 글
| React-Router는 자식 하나만 (0) | 2020.11.09 |
|---|---|
| UITapGestureRecognizer를 사용할 때 탭한 자식보기 찾기 (0) | 2020.11.09 |
| 부트 스트랩 3 : navbar에서 드롭 다운 링크의 헤드를 클릭 할 수있게 만드는 방법 (0) | 2020.11.09 |
| 자바 8 : 스트림 API로 목록 병합 (0) | 2020.11.09 |
| 내 XML 파일에서 BOM 문자를 제거하는 방법 (0) | 2020.11.09 |