번호의 요인을 찾는 데이 코드를 최적화하도록 도와 줄 수 있습니까? 나는 수학 프로그래밍에 솔직 해지고있다.

Question

나는 수학 프로그래밍에 결코 정말로 괴롭지 못했지만, 오늘은 그걸 한 번 줄 것을 결정했다.

여기 내 코드 그리고 그것은 의도 한대로 작동하고 : 내 코드를 볼 수 있습니다

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Windows; 
using System.Windows.Controls; 
using System.Windows.Data; 
using System.Windows.Documents; 
using System.Windows.Input; 
using System.Windows.Media; 
using System.Windows.Media.Imaging; 
using System.Windows.Navigation; 
using System.Windows.Shapes; 

namespace PrimeFactorization 
{ 
    /// <summary> 
    /// Interaction logic for MainWindow.xaml 
    /// </summary> 
    public partial class MainWindow : Window 
    { 
     public MainWindow() 
     { 
      InitializeComponent(); 
     } 

     private void btnSubmit_Click(object sender, RoutedEventArgs e) 
     { 
      List<int> primeFactors = FindPrimeFactors(Convert.ToInt32(txtNumber.Text)); 
      primeFactors.Sort(); 
      for (int i = 0; i < primeFactors.Count; i++) 
      { 
       listBoxFoundNumbers.Items.Add(primeFactors[i]); 
      }    
     } 

     private List<int> FindPrimeFactors(int number) 
     { 
      List<int> factors = new List<int>(); 
      factors.Add(1); 
      factors.Add(number); 

      for (int i = 2; i < number; i++) 
      { 

       if (number % i == 0) 
       { 
        int holder = number/i; 
        //If the number is in the list, don't add it again. 
        if (!factors.Contains(i)) 
        { 
         factors.Add(i); 
        } 
        //If the number is in the list, don't add it again. 
        if (!factors.Contains(holder)) 
        { 
         factors.Add(holder); 
        } 
       }    
      } 

      return factors; 
     } 
    } 
} 

유일한 문제는 확실히 어떤 요인이되지 않더라도, 쓴 끝까지 반복 것입니다.

예를 들어, 내가 35 번에 쓴다고 상상해보십시오. 내 루프가 35 위로 올라가서 24,25,26,27 ... 등을 확인합니다. 아주 좋은하지.

무엇이 좋습니다?

Answer 1

할 수있는 한 가지 방법은 소수가되지 않으므로 2 이후에 짝수를 검사하지 않는 것입니다.

그래서, 2 확인한 다음과 같은 루프를 선언

for (int i = 3; i < number; i+=2) 

재 : sqrt(n)에서 중지 -이 주어진 숫자가 소수 여부를 결정하기위한 효과적인 방법은 x 곳을 분할 어떤 n 때문에,이다 x > sqrt(n)은 또한 sqrt(n)보다 작은 n/x을 나눕니다. 그러나 숫자는 자체 제곱근보다 큰 기본 요소를 가질 수 있습니다 (예 : 1002 = 2 * 3 * 167). 모든 소수에 대한 n 등이 p < sqrt(n)의 p 요인 곳 말했다

, 당신은 또한 n/p의 소인수를 계산, 재귀 솔루션의 일종을 구현할 수 있습니다. 내 직감은 일반적으로 알고리즘의 실행 시간이 줄어들지 만 작은 값이 n 일 때 증가 할 수 있다는 것입니다.

편집 :보다 정교한 기법을 익히려면 Integer Factorization에있는 Wikipedia 페이지에서 모든 종류의 알고리즘에 연결할 수 있습니다.

Answer 2

sqrt(number)까지만 이동할 수 있습니다. x을 2에서 sqrt(N)으로 생각하십시오. N % x == 0 인 경우 N % (N/x) == 0도 마찬가지입니다. 예를 들어 10을 가지고 :

sqrt(10) = 3 (integer part).

10 % 2 == 0 => 2 is a divisor of 10. 10 % (10/2) == 10 % 5 == 0 => 5 is also a divisor.

10 % 3 != 0.

이 그 것이다, 10의 약수이다 2 5. 당신은 완벽한 사각형을 다룰 때 조심해야하고 즉 그것.

수표가 목록에 있는지 여부를 확인하지 않아도됩니다. 완벽한 사각형의 경우 동일한 번호를 두 번 추가하지 마십시오 (x == N/x 인 경우 x 만 추가).

이것은 훨씬 복잡한 알고리즘을 고려하지 않고 얻을만큼 효율적입니다.

편집 : 는 당신이 x 등이 N % x == 0을 발견 할 때, 만 PRIME 요소를 얻을이 가능하지만 x으로 N을 분할합니다. 예를 들어, 20을 고려해

sqrt(20) = 4

20 % 2 == 0 => 2는 주요 요인이다. 2로 나눈 나머지가 더 이상 0이되지 않을 때까지 2로 나눕니다. 0 : 20/2 = 10, 10/2 = 5.

5 % 3 != 0

는

5 % 4 != 0

당신이 알고리즘의 끝 부분에 남아있는 수는 5 > 1, 그래서도 5를 추가합니다. 20의 소인수 그러므로 있습니다 2, 5

그래서 기본적으로 의사의 알고리즘이 있습니다 :

listPrimes(number) 
    N = number; 
    for (i = 2; i <= (int)sqrt(number); ++i) 
    if (N % i == 0) 
     primeFactors.Add(i); 
     while (N % i == 0) 
     N /= i; 

    if (N > 1) 
    primeFactors.Add(N); 

또한 2 시작의 단위를 사용하여, @danben이 자신의 게시물에 제시된 것을 사용할 수 있습니다 3에서 2를 따로 따로 대우하십시오. 그러나 가장 효율적인 방법은 sieve of Eratosthenes을 사용하여 소수를 생성하고 생성 된 소수를이 알고리즘과 함께 사용하는 것입니다. 기본 수학의 세계에 머물면서 가장 효율적입니다.

Answer 3

모든 요소 (소수 만)를 찾으려면 가장 작은 요소 인 k을 찾으면 루프 최대 범위를 n/k까지만 업데이트 할 수 있습니다. 이는 가장 큰 요소 인 l이 p = k * l을 만족해야하기 때문입니다.

더 좋은 접근 방식은 sqrt(n)보다 요인이 더 큰 계산하기 위해 지금까지 발견 한 요소를 사용할 수 있습니다. 그래서, 위의, 당신은 k 및 n에서 직접 l을 계산할 수 있습니다. 소인수를 찾는

Answer 4

한 고전적인 알고리즘 에라 토 스테 네스의 체 (this 참조) 사업의

Answer 5

첫 번째 순서는 적절한 프라임 생성 알고리즘을 사용하는 것입니다. 가장 일반적인 쉽게이기 때문에이 게재됩니다 어떤의 Sieve of Eratosthenes이지만, 또한 훨씬 더 최적화 된 Sieve of Atkin있다.

내가 전에 게시 한 체,이 같은 것을 사용하십시오 :

public static IEnumerable<int> GetPrimeFactors(int num) 
{ 
    return Primes.To(num).Where(i => num % i == 0); 
} 

:

이

public class Primes 
{ 
    public static IEnumerable<int> To(int maxValue) 
    { 
     if (maxValue < 2) 
      return Enumerable.Empty<int>(); 

     bool[] primes = new bool[maxValue + 1]; 
     for (int i = 2; i <= maxValue; i++) 
      primes[i] = true; 

     for (int i = 2; i < Math.Sqrt(maxValue + 1) + 1; i++) 
     { 
      if (primes[i]) 
      { 
       for (int j = i * i; j <= maxValue; j += i) 
        primes[j] = false; 
      } 
     } 

     return Enumerable.Range(2, maxValue - 1).Where(i => primes[i]); 
    } 
} 

마지막 단계는 단지 간단하다 요인, 소수가되는 찾아됩니다

그것의 그! 이렇게하면 1 초도 안되는 시간에 2 천만 개의 프라임 팩터가 생성되므로, 무엇을 하든지 상관없이 충분할 것입니다. 그렇지 않으면 위에서 언급 한 것처럼 더 나은 체를 사용하거나 지연 스킵 세트 알고리즘을 사용할 수 있습니다.

마지막으로 한가지는 : 당신이 다음 거대한 수를 고려하려는 경우에는 General Number Field Sieve과 같은 매우 다른 무언가로 전환 할 필요가있다.RSA 암호화가 해독 될 수 있는지 확인하기위한 지속적인 연구의 일환으로, 이것은 (현재까지 알고있는 바와 같이) 현재 매우 큰 수의 가장 빠른 분해 인수 분해 알고리즘입니다.