数字中最大的素因子

计算数字的最大素数的最好方法是什么？

我认为最有效的将是以下几点：

1. find干净划分的最低质数
2. 检查分割结果是否为素数
3. 如果没有，find下一个最低
4. 转到2。

我基于这个假设更容易计算小素因子。 这是对的吗？ 我应该考虑哪些其他方法？

编辑：我现在已经意识到，如果有两个以上的素数因子在作用，我的方法是徒劳的，因为如果结果是两个其他素数的乘积，则步骤2失败，因此需要recursionalgorithm。

再次编辑：现在我已经意识到，这仍然有效，因为最后find的素数必须是最高的，因此从步骤2开始的任何非素数结果的进一步testing都会导致更小的素数。

Answer 1

实际上有几个更有效的方法来find大数字的因素（对于较小的审判分工工作相当好）。

如果input数字有两个非常接近它的平方根的因素，一个非常快的方法称为费马因式分解 。 它利用了身份N =（a + b）（a – b）= a ^ 2 – b ^ 2，易于理解和实现。 不幸的是，总的来说速度不是很快。

对于长达100位数的因数最有名的方法是二次筛 。 作为奖励，algorithm的一部分很容易通过并行处理完成。

另一个我听说的algorithm是Pollard的Rhoalgorithm 。 一般来说，它不像二次筛分那样高效，但似乎更容易实施。

---

一旦你决定如何将一个数字分成两个因子，下面是我能想到的最快的algorithm来find一个数字的最大的素数因子：

创build一个最初存储号码本身的优先级队列。 每次迭代，你从队列中删除最高的数字，并试图将其分成两个因素（当然，不允许1是这些因素之一）。 如果这一步失败了，那么这个数字就是最好的，你就有了答案！ 否则，您将这两个因素添加到队列中并重复。

Answer 2

这是我所知道的最好的algorithm（在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 

上述方法在最坏情况下（当input是质数时）以O(n)运行。

编辑：
下面是O(sqrt(n))版本，如评论中所build议的。 这是代码，再一次。

 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 

Answer 3

我的答案是基于三联的，但提高了很多。 这是基于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; } 

我最近写了一篇博客文章解释这个algorithm是如何工作的。

我敢打赌，一种不需要进行素性testing（也没有筛分结构）的方法比使用这些方法的方法运行得更快。 如果是这样的话，这可能是这里最快的algorithm。

Answer 4

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

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

你可以简单地从2开始find这些，只是继续划分，直到结果不是你的数字的倍数：

 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. } 

Answer 5

  //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 } 

Answer 6

最简单的解决scheme是一对相互recursion的函数。

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

1. 从包含2以及大于2的所有奇数开始。
2. 删除所有不是素数的数字。 也就是说，没有主要因素的数字（除了他们自己）。 见下文。

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

1. 按升序列出所有的素数（见上）。
2. 设p是该列表中的一个素数， ps是n/p的主要因子（参见步骤1）。
   • 如果p平方大于我们的数n ，那么n是素数。 我们完了。
   • 如果p除以n ，则p是n的主要因子。 其他因素是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 np in if r == 0 then p : factor xs d else factor ps n -- Gives the largest prime factor of its argument largestFactor = last . primeFactors 

Answer 7

被接受的答案已经指出，存在更有效的方法（如二次筛选）来获得给定数量的主要因素，但是如果使用米勒 – 拉宾的帮助， 则试行分割是足够的，并且也是小数目的快速。 因此，我不想用米勒 – 拉宾来展示如何改进审判分工：

注意： Miller-Rabinalgorithm的代码是Rosetta Code的一个改进的稍微改进的版本。 代码使用Python 2.7.8和Python 3.4.1进行了testing

 def int_sqrt(n): x = n y = (x + 1) >> 1 while y < x: x = y y = (x + n // x) >> 1 return x def is_composite(a, d, n, s): if pow(a, d, n) == 1: return False for i in range(s): if pow(a, 2**i * d, n) == n-1: return False return True # n is definitely composite def is_prime(n): if n < 5: if n == 2 or n == 3: return True return False p = n % 6 if p != 1 and p != 5: return False d, s = n - 1, 0 while not d % 2: d, s = d >> 1, s + 1 if n < 2047: return not is_composite(2, d, n, s) if n < 1373653: return not any(is_composite(a, d, n, s) for a in (2, 3)) if n < 9080191: return not any(is_composite(a, d, n, s) for a in (31, 73)) if n < 25326001: return not any(is_composite(a, d, n, s) for a in (2, 3, 5)) if n < 118670087467: if n == 3215031751: return False return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7)) if n < 2152302898747: return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11)) if n < 3474749660383: return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13)) if n < 341550071728321: return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17)) if n < 3825123056546413051: return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17, 19, 23)) return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53)) def factorize(n): factors = [] if n < 2: return factors if is_prime(n): factors.append(n) return factors while n % 2 == 0: n >>= 1 factors.append(2) if n == 1: return factors max = int_sqrt(n) + 1 i = 3 while i < max: while n % i == 0: n = n // i factors.append(i) if n == 1: return factors if is_prime(n): factors.append(n) return factors i += 2 return [] print(factorize(98768765456789876)) 

输出是：

 [2, 2, 7, 23, 153367648224829] 

Answer 8

我知道这不是一个快速的解决scheme。 张贴希望更容易理解缓慢的解决scheme。

  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; } 

Answer 9

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); 

这是一个代码示例 ：

Answer 10

 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) 

有一些模数testing是过分的，因为如果所有因素2和3都被删除，n永远不能被6除。 你只能让我的素数，这在其他几个答案中显示。

你实际上可以在这里交织Eratosthenes的筛子：

• 首先创buildsqrt（n）的整数列表。
• 在for循环中，将我的所有倍数都标记为不是素数的新sqrt（n），而是使用while循环。
• 将我设置为列表中的下一个素数。

也看到这个问题 。

Answer 11

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 

Answer 12

我正在使用algorithm继续将其数目除以当前的素数。

我的解决scheme在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 ie 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()))) 

input： 10输出： 5

input： 600851475143输出： 6857

Answer 13

这里是我的方法来快速计算最大的素因子。 这是基于修改后的x不包含非素数因素的事实。 为了达到这个目的，一旦find一个因子，我们就把x除。 那么，唯一剩下的就是回归最大的因素。 这将是最重要的。

代码（Haskell）：

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

Answer 14

下面的C ++algorithm并不是最好的，但是对于数量不到十亿的数字来说，这个algorithm是相当快的

 #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; } // ----- MAIN ------ 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; } 

Answer 15

在我看来，给出的algorithm的第二步不会是一个有效的方法。 你没有合理的期望，这是最重要的。

另外，以前的答案build议Eratosthenes筛是完全错误的。 我只写了两个程序123456789因素。一个是基于筛，一个是基于以下：

 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倍。

问题是，在现代处理器上，操作的types远远less于操作的数量，更不用说上面的algorithm可以在caching中运行，Sieve不能。 Sieve使用了大量的操作来打出所有的合成数字。

另外请注意，我确定的分解因素减less了必须testing的空间。

Answer 16

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

每当你素数分解一个数字，使用三联实现，但迭代素数的列表，而不是自然整数。

Answer 17

这是我在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; } } } 

Answer 18

使用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; } 

Answer 19

 #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 

Answer 20

使用C ++中的recursion计算数字的最大素数因子。 代码的工作原理如下：

 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 } 

Answer 21

我认为将所有可能的素数存储在小于n的地方是很好的，只要遍历它们就可以find最大的差异。 你可以从prime-numbers.org获得素数。

当然，我认为你的号码不是太大:)

Answer 22

这可能并不总是更快，但更乐观的是你find了一个很大的主要因数：

1. N是你的号码
2. 如果是素数，则return(N)
3. 计算素数直到Sqrt(N)
4. 按照降序排列（最大的）
   • 如果N is divisible by Prime则Return(Prime)

编辑：在第3步，你可以使用Eratosthenes筛或阿特金斯筛或任何你喜欢的，但它本身筛不会find你最大的主要因素。 （这就是为什么我不会selectSQLMenace的职位作为正式答案…）

Answer 23

不是最快的，但它的工作原理！

  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; } 

Answer 24

下面是作为发生器提供的同样的function@三联，它也被简化了一些。

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

然后可以使用以下命令find最大素数：

 n= 373764623 max(primes(n)) 

以及使用以下的一系列因素：

 list(primes(n)) 

Answer 25

 #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(); }