M보다 큰 첫 번째 숫자 찾기 M

기본적으로 제목은 모든 것을 말합니다. 숫자가 너무 크지 않습니다 (최대 N은 최대 2/3 * 최대 (긴)이고 최대 M은 최대 (긴)입니다), 그래서 나는 현재 가지고있는 간단한 해결책조차도 충분하다고 생각합니다. M은 N. 것보다 항상 더 큰M보다 큰 첫 번째 숫자 찾기 M

내가 현재 무엇을 가지고 :

대부분 단순, 그냥 1을 반환하는 경우 증가하지 않을 경우, 우리는, 완료 N + 1, 일반 유클리드 GCD을 수행 시작하고, 그리고 다시 시도하십시오.

이 솔루션의 최악의 시나리오는 무엇입니까? 성능은 큰 문제는 아니지만 더 나은 방법이 있어야하는 것처럼 느껴집니다.

감사합니다.

Random r = new Random(); 
while (true) 
      { 
       long num = (long) r.Next(); 
       num *= r.Next(); 
       f((long)(num * 0.61), num); 
      } 

... 

public static int max; 

     public static int f(long N, long M) 
     { 
      int iter = 0; 
      while (GCD(N++, M) != 1) 
      { 
       iter++; 
      } 

      if (iter > max) 
      { 
       max = iter; 
       Console.WriteLine(max); 
      } 

      return 0; 
     }

그것은에 대한 실행 ~ 30 분까지 최악의 경우가 29 번 반복 : 최악의 경우에 대해

, 나는 작은 시험을했다. 그래서 저는 O (N)보다 더 정확한 대답이 있다고 믿습니다.

는

출처

2012-02-01 Klark

I가 M < 2 ⁶⁴, 난 비 N/M은 대략 고정하는 제한을 제거 (53 292 반복 아래 이상을 결합 할 수있는 최악의 시나리오를 알고 있지만, 사실을 이용하지). ... P K가 M보다 크거나 나눌 수있는 5와 동일한 수 소수 ₁

P하자. N '= 1 mod 6 또는 N'= 5 mod 6이되도록 N '≥ N을 최소 정수 라하자. 각 i = 1, ..., k에 대해 프라임 p _i은 최대 ceil (49/p _{N '+ 6, N'+ 12, ..., N '+ 288)의 상한은이다. Σ _{I = 3, ..., 16} CEIL Q는 Q로 시작하는 순서로 소수 인 (49/Q _I) = 48 ₁ = 2 (이 따르기 때문에 Π _{I = 3, ... 17} ≥ 2 은 M이 2와 3을 제외한 최대 14 개의 별 소수의 결과임을 의미합니다.) 결론 언급 된 정수들 중 적어도 하나가 M에 대해 상대적으로 소수라는 것.}

M = 614889782588491410 (첫 15 개의 소수의 결과) N = 1로 놓는다. 1 후에, 첫 번째 정수는 처음 15 개 소수는 16 번째 프라임입니다.

두 가지 경계는 너무 많은 작업 없이도 개선 될 수 있다고 예상합니다. 그러나 어떤 목적 으로든 명확하지 않습니다. 상한선에 대해, 2와 3이 M의 약수 인 경우를 별도로 처리한다. 그러면 M은 기껏해야 0의 곱이 될 수있다. 13 번 다른 소수. 하한에 대해서 에라 토 스테 네스 (Eratosthenes)의 체를 실행하여 정수의 범위에 대해 정수를 나눌 수있는 소수 목록을 계산하여 좋은 M을 찾으려고 할 수 있습니다. 그런 다음 범위를 가로 질러 창을 쓸어 넘기십시오. 창에있는 별개의 소수의 결과가 너무 큰 경우, 창의 마지막 끝을 앞으로 나아가십시오. 그렇지 않으면 선단을 진행하십시오.를 n 우리는 단순히 대부분이 때문에 대부분의에서 통과 한 후 (_전자 N 반복, 로그에서 당신의 알고리즘을 가지고 말할 수 _{전자 로그는 소수의 간격이 _{전자에게 로그인 것을 알면, O (n)이 아니다 물론}}

출처

2012-02-01 15:26:07 swen

n 번호는 주어진 숫자에 가장 가까운 새로운 소수를 볼 것입니다 n)이 차이에 대한 자세한 내용은 prime numbers gap을 참조하십시오.

는 그래서 제한된 경우에 N _E 로그 = _E ² < 64 = 44을 기록하고 미만 44 반복 것보다 작다.

출처

2012-02-01 17:31:22

M보다 큰 첫 번째 숫자 찾기 M

답변

관련 문제