首页 文章

查找数字的最大素数因子的算法

提问于
浏览
169

计算数字中最大素数因子的最佳方法是什么?

我认为最有效的将是以下内容:

  • 找到干净分割的最低素数

  • 检查除法结果是否为素数

  • 如果没有,找到下一个最低点

  • 转到2 .

我基于这个假设,因为它更容易计算小素因子 . 这是对的吗?我应该研究哪些其他方法?

编辑:我现在已经意识到,如果有超过2个素因子,我的方法是徒劳的,因为当结果是两个其他素数的乘积时,步骤2失败,因此需要递归算法 .

再次编辑:现在我已经意识到这仍然有效,因为最后找到的素数必须是最高的,因此对步骤2的非素数结果的任何进一步测试都会导致较小的素数 .

27 回答

  • 1

    通过“James Wang”在网上找到这个解决方案

    public static int getLargestPrime( int number) {
    
        if (number <= 1) return -1;
    
        for (int i = number - 1; i > 1; i--) {
            if (number % i == 0) {
                number = i;
            }
        }
        return number;
    }
    
  • 17

    实际上,有几种更有效的方法可以找到大数的因子(对于较小的因子,试验分工合理地工作得很好) .

    如果输入数字具有非常接近其平方根的两个因子,则一种非常快的方法称为Fermat factorisation . 它利用身份N =(a b)(a - b)= a ^ 2 - b ^ 2,易于理解和实现 . 不幸的是,它一般来说不是很快 .

    用于将数字分解为最多100位数的最着名的方法是Quadratic sieve . 作为奖励,部分算法可以通过并行处理轻松完成 .

    我听说的另一种算法是Pollard's Rho algorithm . 它一般不如Quadratic Sieve有效,但似乎更容易实现 .


    一旦你决定如何将一个数字分成两个因子,这里是我能想到的最快的算法,找到一个数字的最大素数因子:

    创建一个最初存储数字本身的优先级队列 . 每次迭代,您从队列中删除最高的数字,并尝试将其分成两个因子(当然,不允许1成为这些因素之一) . 如果此步骤失败,则数字为素数,您就有了答案!否则,将两个因子添加到队列中并重复 .

  • 2

    这是我所知道的最好的算法(在Python中)

    def prime_factors(n):
        """Returns all the prime factors of a positive integer"""
        factors = []
        d = 2
        while n > 1:
            while n % d == 0:
                factors.append(d)
                n /= d
            d = d + 1
    
        return factors
    
    
    pfs = prime_factors(1000)
    largest_prime_factor = max(pfs) # The largest element in the prime factor list
    

    在最坏的情况下(当输入是素数时),上述方法在 O(n) 中运行 .

    EDIT:
    以下是评论中建议的 O(sqrt(n)) 版本 . 这是代码,再一次 .

    def prime_factors(n):
        """Returns all the prime factors of a positive integer"""
        factors = []
        d = 2
        while n > 1:
            while n % d == 0:
                factors.append(d)
                n /= d
            d = d + 1
            if d*d > n:
                if n > 1: factors.append(n)
                break
        return factors
    
    
    pfs = prime_factors(1000)
    largest_prime_factor = max(pfs) # The largest element in the prime factor list
    
  • -1

    我的答案基于Triptych,但在其上有很大的改进 . 它基于超过2和3的事实,所有素数都是6n-1或6n 1的形式 .

    var largestPrimeFactor;
    if(n mod 2 == 0)
    {
        largestPrimeFactor = 2;
        n = n / 2 while(n mod 2 == 0);
    }
    if(n mod 3 == 0)
    {
        largestPrimeFactor = 3;
        n = n / 3 while(n mod 3 == 0);
    }
    
    multOfSix = 6;
    while(multOfSix - 1 <= n)
    {
        if(n mod (multOfSix - 1) == 0)
        {
            largestPrimeFactor = multOfSix - 1;
            n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
        }
    
        if(n mod (multOfSix + 1) == 0)
        {
            largestPrimeFactor = multOfSix + 1;
            n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
        }
        multOfSix += 6;
    }
    

    我最近写了一个blog article来解释这个算法是如何工作的 .

    我敢说,一种不需要进行素数测试(并且没有筛子构造)的方法比使用那些方法的方法运行得更快 . 如果是这种情况,这可能是这里最快的算法 .

  • 2

    所有数字都可以表示为素数的乘积,例如:

    102 = 2 x 3 x 17
    712 = 2 x 2 x 2 x 89
    

    您只需从2开始,只需继续划分直到结果不是您的数字的倍数即可找到这些:

    712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1
    

    使用这种方法你不必实际计算任何素数:它们都是素数,基于你已经使用所有前面的数字尽可能多地将数字分解的事实 .

    number = 712;
    currNum = number;    // the value we'll actually be working with
    for (currFactor in 2 .. number) {
        while (currNum % currFactor == 0) {
            // keep on dividing by this number until we can divide no more!
            currNum = currNum / currFactor     // reduce the currNum
        }
        if (currNum == 1) return currFactor;    // once it hits 1, we're done.
    }
    
  • 0
    //this method skips unnecessary trial divisions and makes 
        //trial division more feasible for finding large primes
    
        public static void main(String[] args) 
        {
            long n= 1000000000039L; //this is a large prime number 
            long i = 2L;
            int test = 0;
    
            while (n > 1)
            {
                while (n % i == 0)
                {
                    n /= i;     
                }
    
                i++;
    
                if(i*i > n && n > 1) 
                {
                    System.out.println(n); //prints n if it's prime
                    test = 1;
                    break;
                }
            }
    
            if (test == 0)  
                System.out.println(i-1); //prints n if it's the largest prime factor
        }
    
  • 127

    JavaScript代码:

    'option strict';
    
    function largestPrimeFactor(val, divisor = 2) { 
        let square = (val) => Math.pow(val, 2);
    
        while ((val % divisor) != 0 && square(divisor) <= val) {
            divisor++;
        }
    
        return square(divisor) <= val
            ? largestPrimeFactor(val / divisor, divisor)
            : val;
    }
    

    用法示例:

    let result = largestPrimeFactor(600851475143);
    

    Here is an example of the code

  • -3

    类似@Triptych的回答也不同 . 在此示例中,不使用列表或字典 . 代码是用Ruby编写的

    def largest_prime_factor(number)
      i = 2
      while number > 1
        if number % i == 0
          number /= i;
          i -= 1
        end
        i += 1
      end
      return i
    end
    
    largest_prime_factor(600851475143)
    # => 6857
    
  • -3

    最简单的解决方案是一对相互递归的函数 .

    第一个函数生成所有素数:

    • 以包含2和所有大于2的奇数的列表开头 .

    • 删除所有不是素数的数字 . 也就是说,没有素数因素的数字(除了他们自己) . 见下文 .

    第二个函数按递增顺序返回给定数字 n 的素数因子 . 策略是试图将每个可能是其除数的素数除以 n

    • 按递增顺序列出所有素数(见上文) .

    • p 是该列表中的素数, psn/p 的主要因子(参见步骤1) .

    • 如果 p 平方大于我们的数字 n ,那么 n 是素数 . 我们完了 .

    • 如果 pn ,那么 pn 的主要因子 . 其他因素是 ps .

    • 否则 p 不是 n 的主要因素 .

    n 的最大素数因子是第二个函数给出的最后一个数字 .

    为了澄清,这里是上面的代码,在Haskell中:

    import Control.Monad
    
    -- All the primes
    primes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..]
    
    -- Gives the prime factors of its argument
    primeFactors = factor primes
      where factor [] n = []
            factor xs@(p:ps) n =
              if p*p > n then [n]
              else let (d,r) = divMod n p in
                if r == 0 then p : factor xs d
                else factor ps n
    
    -- Gives the largest prime factor of its argument
    largestFactor = last . primeFactors
    
  • -3
    n = abs(number);
    result = 1;
    if (n mod 2 == 0) {
      result = 2;
      while (n mod 2 = 0) n /= 2;
    }
    for(i=3; i<sqrt(n); i+=2) {
      if (n mod i == 0) {
        result = i;
        while (n mod i = 0)  n /= i;
      }
    }
    return max(n,result)
    

    有一些模数测试是超级的,因为如果所有因子2和3都已被删除,则n永远不能除以6 . 你只能允许i的素数,这在其他几个答案中显示 .

    你真的可以在这里交织了Eratosthenes的筛子:

    • 首先创建最大为sqrt(n)的整数列表 .

    • 在for循环中标记i的所有倍数,直到新的sqrt(n)为非素数,并使用while循环 .

    • 将i设置为列表中的下一个素数 .

    另见this question .

  • 4

    我知道这不是一个快速的解决方案 . 发布希望更容易理解缓慢的解决方案 .

    public static long largestPrimeFactor(long n) {
    
            // largest composite factor must be smaller than sqrt
            long sqrt = (long)Math.ceil(Math.sqrt((double)n));
    
            long largest = -1;
    
            for(long i = 2; i <= sqrt; i++) {
                if(n % i == 0) {
                    long test = largestPrimeFactor(n/i);
                    if(test > largest) {
                        largest = test;
                    }
                }
            }
    
            if(largest != -1) {
                return largest;
            }
    
            // number is prime
            return n;
        }
    
  • 0

    Python迭代方法,从数字中删除所有素数因子

    def primef(n):
        if n <= 3:
            return n
        if n % 2 == 0:
            return primef(n/2)
        elif n % 3 ==0:
            return primef(n/3)
        else:
            for i in range(5, int((n)**0.5) + 1, 6):
                #print i
                if n % i == 0:
                    return primef(n/i)
                if n % (i + 2) == 0:
                    return primef(n/(i+2))
        return n
    
  • -1

    我正在使用算法继续将数字除以当前的Prime因子 .

    我在python 3中的解决方案:

    def PrimeFactor(n):
        m = n
        while n%2==0:
            n = n//2
        if n == 1:         # check if only 2 is largest Prime Factor 
            return 2
        i = 3
        sqrt = int(m**(0.5))  # loop till square root of number
        last = 0              # to store last prime Factor i.e. Largest Prime Factor
        while i <= sqrt :
            while n%i == 0:
                n = n//i       # reduce the number by dividing it by it's Prime Factor
                last = i
            i+=2
        if n> last:            # the remaining number(n) is also Factor of number 
            return n
        else:
            return last
    print(PrimeFactor(int(input())))
    

    输入: 10 输出: 5

    输入: 600851475143 输出: 6857

  • 4

    这是我在c#中的尝试 . 最后一次打印输出是该数字的最大主要因素 . 我检查了它的确有效 .

    namespace Problem_Prime
    {
      class Program
      {
        static void Main(string[] args)
        {
          /*
           The prime factors of 13195 are 5, 7, 13 and 29.
    
          What is the largest prime factor of the number 600851475143 ?
           */
          long x = 600851475143;
          long y = 2;
          while (y < x)
          {
            if (x % y == 0)
            {
              // y is a factor of x, but is it prime
              if (IsPrime(y))
              {
                Console.WriteLine(y);
              }
              x /= y;
            }
    
            y++;
    
          }
          Console.WriteLine(y);
          Console.ReadLine();
        }
        static bool IsPrime(long number)
        {
          //check for evenness
          if (number % 2 == 0)
          {
            if (number == 2)
            {
              return true;
            }
            return false;
          }
          //don't need to check past the square root
          long max = (long)Math.Sqrt(number);
          for (int i = 3; i <= max; i += 2)
          {
            if ((number % i) == 0)
            {
              return false;
            }
          }
          return true;
        }
    
      }
    }
    
  • -2
    #python implementation
    import math
    n = 600851475143
    i = 2
    factors=set([])
    while i<math.sqrt(n):
       while n%i==0:
           n=n/i
           factors.add(i)
       i+=1
    factors.add(n)
    largest=max(factors)
    print factors
    print largest
    
  • 3

    使用C中的递归计算数字的最大素因子 . 代码的工作原理如下:

    int getLargestPrime(int number) {
        int factor = number; // assumes that the largest prime factor is the number itself
        for (int i = 2; (i*i) <= number; i++) { // iterates to the square root of the number till it finds the first(smallest) factor
            if (number % i == 0) { // checks if the current number(i) is a factor
                factor = max(i, number / i); // stores the larger number among the factors
                break; // breaks the loop on when a factor is found
            }
        }
        if (factor == number) // base case of recursion
            return number;
        return getLargestPrime(factor); // recursively calls itself
    }
    
  • 0

    这是我快速计算最大素因子的方法 . 它基于以下事实:修改后的 x 不包含非素因子 . 为实现这一目标,我们会在找到因素时立即划分 x . 然后,唯一剩下的就是返回最大因子 . 它已经是素数了 .

    代码(Haskell):

    f max' x i | i > x = max'
               | x `rem` i == 0 = f i (x `div` i) i  -- Divide x by its factor
               | otherwise = f max' x (i + 1)  -- Check for the next possible factor
    
    g x = f 2 x 2
    
  • 0

    以下C算法不是最好的算法,但它适用于十亿以下的数字并且速度非常快

    #include <iostream>
    using namespace std;
    
    // ------ is_prime ------
    // Determines if the integer accepted is prime or not
    bool is_prime(int n){
        int i,count=0;
        if(n==1 || n==2)
          return true;
        if(n%2==0)
          return false;
        for(i=1;i<=n;i++){
        if(n%i==0)
            count++;
        }
        if(count==2)
          return true;
        else
          return false;
     }
     // ------ nextPrime -------
     // Finds and returns the next prime number
     int nextPrime(int prime){
         bool a = false;
         while (a == false){
             prime++;
             if (is_prime(prime))
                a = true;
         }
      return prime;
     }
     // ----- M A I N ------
     int main(){
    
          int value = 13195;
          int prime = 2;
          bool done = false;
    
          while (done == false){
              if (value%prime == 0){
                 value = value/prime;
                 if (is_prime(value)){
                     done = true;
                 }
              } else {
                 prime = nextPrime(prime);
              }
          }
            cout << "Largest prime factor: " << value << endl;
     }
    
  • 4

    Prime factor using sieve :

    #include <bits/stdc++.h>
    using namespace std;
    #define N 10001  
    typedef long long ll;
    bool visit[N];
    vector<int> prime;
    
    void sieve()
    {
                memset( visit , 0 , sizeof(visit));
                for( int i=2;i<N;i++ )
                {
                    if( visit[i] == 0)
                    {
                        prime.push_back(i);
                        for( int j=i*2; j<N; j=j+i )
                        {
                            visit[j] = 1;
                        }
                    }
                }   
    }
    void sol(long long n, vector<int>&prime)
    {
                ll ans = n;
                for(int i=0; i<prime.size() || prime[i]>n; i++)
                {
                    while(n%prime[i]==0)
                    {
                        n=n/prime[i];
                        ans = prime[i];
                    }
                }
                ans = max(ans, n);
                cout<<ans<<endl;
    }
    int main() 
    {
               ll tc, n;
               sieve();
    
               cin>>n;
               sol(n, prime);
    
               return 0;
    }
    
  • 0

    在我看来,给出的算法的第二步并不是那种有效的方法 . 你没有合理的期望它是素数 .

    此外,之前的答案暗示了Eratosthenes的筛子是完全错误的 . 我刚写了两个程序来考虑123456789.一个基于Sieve,一个是基于以下内容:

    1)  Test = 2 
    2)  Current = Number to test 
    3)  If Current Mod Test = 0 then  
    3a)     Current = Current Div Test 
    3b)     Largest = Test
    3c)     Goto 3. 
    4)  Inc(Test) 
    5)  If Current < Test goto 4
    6)  Return Largest
    

    这个版本比Sieve快90倍 .

    问题是,在现代处理器上,操作类型远远少于操作数量,更不用说上面的算法可以在缓存中运行,而Sieve则不能 . Sieve使用大量操作来识别所有复合数字 .

    另请注意,我识别出的因素会减少必须测试的空间 .

  • 0

    首先计算存储素数的列表,例如2 3 5 7 11 13 ...

    每当你对一个数字进行分解时,使用Triptych的实现,但是迭代这个素数列表而不是自然整数 .

  • 0

    使用Java:

    对于 int 值:

    public static int[] primeFactors(int value) {
        int[] a = new int[31];
        int i = 0, j;
        int num = value;
        while (num % 2 == 0) {
            a[i++] = 2;
            num /= 2;
        }
        j = 3;
        while (j <= Math.sqrt(num) + 1) {
            if (num % j == 0) {
                a[i++] = j;
                num /= j;
            } else {
                j += 2;
            }
        }
        if (num > 1) {
            a[i++] = num;
        }
        int[] b = Arrays.copyOf(a, i);
        return b;
    }
    

    对于 long 值:

    static long[] getFactors(long value) {
        long[] a = new long[63];
        int i = 0;
        long num = value;
        while (num % 2 == 0) {
            a[i++] = 2;
            num /= 2;
        }
        long j = 3;
        while (j <= Math.sqrt(num) + 1) {
            if (num % j == 0) {
                a[i++] = j;
                num /= j;
            } else {
                j += 2;
            }
        }
        if (num > 1) {
            a[i++] = num;
        }
        long[] b = Arrays.copyOf(a, i);
        return b;
    }
    
  • 1

    这可能并不总是更快,但更乐观的是你找到了一个重要的除数:

    • N 是你的号码

    • 如果是素数那么 return(N)

    • 计算素数直到 Sqrt(N)

    • 按降序排列素数(最大的第一个)

    • 如果 N is divisible by Prime 那么 Return(Prime)

    编辑:在第3步中,您可以使用Eratosthenes的筛子或阿特金斯筛子或任何您喜欢的筛子,但筛子本身并不会找到最重要的因素 . (这就是为什么我不会选择SQLMenace的帖子作为正式答案......)

  • 128

    我认为将所有可能的素数存储在小于n的位置并且只是遍历它们以找到最大的分数是很好的 . 你可以从prime-numbers.org获得素数 .

    当然我假设你的号码不是太大:)

  • -1

    不是最快但是有效!

    static bool IsPrime(long num)
        {
            long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
            for (long i = 2; i <= checkUpTo; i++)
            {
                if (num % i == 0)
                    return false;
            }
            return true;
        }
    
  • 4

    这是@ Triptych作为发生器提供的相同功能,它也略有简化 .

    def primes(n):
        d = 2
        while (n > 1):
            while (n%d==0):
                yield d
                n /= d
            d += 1
    

    然后可以使用以下命令找到最大素数:

    n= 373764623
    max(primes(n))
    

    以及使用以下内容找到的因素列表:

    list(primes(n))
    
  • -6
    #include<stdio.h>
    #include<conio.h>
    #include<math.h>
    #include <time.h>
    
    factor(long int n)
    {
    long int i,j;
    while(n>=4)
     {
    if(n%2==0) {  n=n/2;   i=2;   }
    
     else
     { i=3;
    j=0;
      while(j==0)
      {
       if(n%i==0)
       {j=1;
       n=n/i;
       }
       i=i+2;
      }
     i-=2;
     }
     }
    return i;
     }
    
     void main()
     { 
      clock_t start = clock();
      long int n,sp;
      clrscr();
      printf("enter value of n");
      scanf("%ld",&n);
      sp=factor(n);
      printf("largest prime factor is %ld",sp);
    
      printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
      getch();
     }
    

相关问题