小开

我认为最好将所有可能的小于n的素数存储在某个地方，然后迭代它们以找到最大的除数。你可以从__abc0中得到素数。

当然，我假设你的数字不是太大：）

小开

这可能并不总是更快，但更乐观，你会发现一个大的质除数：

N是你的号码
如果它是素数，那么__abc0
计算直到Sqrt(N)的素数
排列素数（最大的在前）
- 如果N is divisible by Prime，则Return(Prime)

编辑：在第3步中，你可以使用埃拉托色尼的筛子或阿特金斯的筛子或任何你喜欢的东西，但筛子本身不会为你找到最大的质因数。（这就是为什么我不会选择SqlMenace的帖子作为官方答案……

小开

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为素数，这在这里的其他几个答案中显示。

你可以把埃拉托色尼的筛子缠绕在一起：

首先创建整数列表 sqrt(n).
在for循环中，标记所有倍数直到新的sqrt(n)为止 Prime，并改为使用while循环。
i设置为中的下一个素数名单.

另请参阅这个问题。

小开

最佳答案

实际上，有几种更有效的方法可以找到大数的因子（对于较小的因子，试验除法效果相当好）。

如果输入数具有两个非常接近其平方根的因子，则非常快的一种方法被称为费马分解。它利用了恒等式n=（a+B）（a-B）=a^2-B^2，并且易于理解和实现。不幸的是，它总体上不是很快。

分解最多100位数字的最著名的方法是二次筛。作为奖励，算法的一部分很容易通过并行处理来完成。

我听说过的另一种算法是波拉德的Rho算法。一般来说，它不像二次筛法那样有效，但似乎更容易实现。

一旦你决定了如何将一个数字拆分成两个因子，下面是我能想到的找到一个数字的最大素因子的最快算法：

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

小开

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

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

首先列出所有大于1的自然数。
删除所有不是质数的数字。即没有质因数的数（除了它们本身）。见下文。

第二个函数按升序返回给定数字n的素因子。

列出所有素数（见上文）。
去掉所有不是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

要使其更快，只需更聪明地检测哪些数字是素数和/或n的因子，但算法保持不变。

小开

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

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

小开

在我看来，给出的算法的步骤#2并不是一种有效的方法。你没有合理的期望它是质数。

此外，前面的答案暗示埃拉托色尼的筛子是完全错误的。我刚刚编写了两个程序来分解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

这个版本比筛子快90倍。

问题是，在现代处理器上，运算类型远不如运算数量重要，更不用说上面的算法可以在缓存中运行，而筛子却不能。筛子用了很多运算，把所有的合数都划掉了。

还要注意的是，我在确定因素时将其划分出来，减少了必须测试的空间。

小开

下面是我所知道的最好的算法（在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)中运行。

编辑：
下面是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

小开

我的答案是基于三联画的，但改进了很多。它是基于这样的事实，即在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;
}

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

我冒昧地说，一种不需要素性测试（也没有筛子构造）的方法会比使用这些方法的方法运行得更快。如果是这样的话，这可能是这里最快的算法。

小开

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

小开

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

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

小开

下面是作为生成器提供的相同函数@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))

小开

首先计算存储素数的列表，例如23571113。

每次对一个数字进行素数分解时，使用三联图实现，但迭代这个素数列表，而不是自然整数。

小开

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


}
}

小开

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

小开

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

小开

#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

小开

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

小开

通过从数字中删除所有素因子的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

小开

下面是我快速计算最大素因子的方法。它基于修正的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

小开

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

下面是一个代码示例：

小开

下面的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;
}

小开

我使用的算法是继续将数字除以它的当前素因子。

我在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

小开

类似于@三联画答案，但也不同。在此示例中，未使用列表或字典。代码是用Ruby编写的

def largest_prime_factor(number)
i = 2
while number > 1
if number % i == 0
number /= i;
else
i += 1
end
end
return i
end


largest_prime_factor(600851475143)
# => 6857

小开

“ James Wang ”在Web上找到了此解决方案

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

小开

使用筛子的质因数：

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

小开

下面是我在Clojure中的尝试。只走prime?的几率和素因子的素数，即sieve。使用惰性序列有助于在需要值之前生成这些值。

(defn prime?
([n]
(let [oddNums (iterate #(+ % 2) 3)]
(prime? n (cons 2 oddNums))))
([n [i & is]]
(let [q (quot n i)
r (mod n i)]
(cond (< n 2)       false
(zero? r)     false
(> (* i i) n) true
:else         (recur n is)))))


(def primes
(let [oddNums (iterate #(+ % 2) 3)]
(lazy-seq (cons 2 (filter prime? oddNums)))))


;; Sieve of Eratosthenes
(defn sieve
([n]
(sieve primes n))
([[i & is :as ps] n]
(let [q (quot n i)
r (mod n i)]
(cond (< n 2)       nil
(zero? r)     (lazy-seq (cons i (sieve ps q)))
(> (* i i) n) (when (> n 1) (lazy-seq [n]))
:else         (recur is n)))))


(defn max-prime-factor [n]
(last (sieve n)))

小开

我猜，除了执行因式分解之外，没有其他直接的方法，正如上面的例子所做的那样，即

在迭代中，您确定了一个“小”名词的数的因子F，然后继续简化问题求N：=N/F的最大素因子，其候选因子>；=F。

从一定大小的F来看，如果对约化N进行素性测试，则预期的搜索时间较少，这在某种情况下证实了您的N已经是初始名词的最大素因子。

小开

受到您的问题的启发，我决定在Python中实现我自己的因式分解版本（并找到最大素因子）。

可能是最简单的实现，但相当有效，因子分解算法，我知道是波拉德的Rho算法。它的运行时间最多为O(N^(1/4))，比O(N^(1/2))的尝试分割算法快得多。这两个算法只有在合数（非素数）的情况下才有这些运行时间，这就是为什么应该使用素性测试来过滤素数（不可分解）。

我在代码中使用了以下算法：费马素性检验.，波拉德的Rho算法.，试分算法。费马素性测试是在运行波拉德的Rho之前使用的，目的是过滤掉素数。审判部门被用作后备，因为波拉德的Rho在非常罕见的情况下可能无法找到一个因素，特别是对于一些小的数字。

显然，在将一个数完全分解为素因子的排序列表之后，最大的素因子将是该列表中的最后一个元素。在一般情况下（对于任何随机数），除了完全因式分解一个数之外，我不知道有任何其他方法可以找出最大素因子。

例如，在我的代码中，我正在分解圆周率的第一个190小数数字，代码在1秒内分解这个数字，并显示最大的素数因子，其大小165数字（545位）。

在网上试试吧！

def is_fermat_probable_prime(n, *, trials = 32):
# https://en.wikipedia.org/wiki/Fermat_primality_test
import random
if n <= 16:
return n in (2, 3, 5, 7, 11, 13)
for i in range(trials):
if pow(random.randint(2, n - 2), n - 1, n) != 1:
return False
return True


def pollard_rho_factor(N, *, trials = 16):
# https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
import random, math
for j in range(trials):
i, stage, y, x = 0, 2, 1, random.randint(1, N - 2)
while True:
r = math.gcd(N, x - y)
if r != 1:
break
if i == stage:
y = x
stage <<= 1
x = (x * x + 1) % N
i += 1
if r != N:
return [r, N // r]
return [N] # Pollard-Rho failed


def trial_division_factor(n, *, limit = None):
# https://en.wikipedia.org/wiki/Trial_division
fs = []
while n & 1 == 0:
fs.append(2)
n >>= 1
d = 3
while d * d <= n and limit is None or d <= limit:
q, r = divmod(n, d)
if r == 0:
fs.append(d)
n = q
else:
d += 2
if n > 1:
fs.append(n)
return fs


def factor(n):
if n <= 1:
return []
if is_fermat_probable_prime(n):
return [n]
fs = trial_division_factor(n, limit = 1 << 12)
if len(fs) >= 2:
return sorted(fs[:-1] + factor(fs[-1]))
fs = pollard_rho_factor(n)
if len(fs) >= 2:
return sorted([e1 for e0 in fs for e1 in factor(e0)])
return trial_division_factor(n)


def demo():
import time, math
# http://www.math.com/tables/constants/pi.htm
# pi = 3.
#     1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679
#     8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196
# n = first 190 fractional digits of Pi
n =   1415926535_8979323846_2643383279_5028841971_6939937510_5820974944_5923078164_0628620899_8628034825_3421170679_8214808651_3282306647_0938446095_5058223172_5359408128_4811174502_8410270193_8521105559_6446229489
print('Number:', n)
tb = time.time()
fs = factor(n)
print('All Prime Factors:', fs)
print('Largest Prime Factor:', f'({math.log2(fs[-1]):.02f} bits, {len(str(fs[-1]))} digits)', fs[-1])
print('Time Elapsed:', round(time.time() - tb, 3), 'sec')


if __name__ == '__main__':
demo()

产量：

Number: 1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489
All Prime Factors: [3, 71, 1063541, 153422959, 332958319, 122356390229851897378935483485536580757336676443481705501726535578690975860555141829117483263572548187951860901335596150415443615382488933330968669408906073630300473]
Largest Prime Factor: (545.09 bits, 165 digits) 122356390229851897378935483485536580757336676443481705501726535578690975860555141829117483263572548187951860901335596150415443615382488933330968669408906073630300473
Time Elapsed: 0.593 sec

小开

C语言中的递归

算法可能是

检查n是因子还是t
检查n是否为素数。如果是这样，请记住N
增量N
重复直到N>；SQRT（T）

下面是C语言中该问题的（尾部）递归解决方案的示例：

#include <stdio.h>
#include <stdbool.h>


bool is_factor(long int t, long int n){
return ( t%n == 0);
}


bool is_prime(long int n0, long int n1, bool acc){
if ( n1 * n1 > n0 || acc < 1 )
return acc;
else
return is_prime(n0, n1+2, acc && (n0%n1 != 0));
}


int gpf(long int t, long int n, long int acc){
if (n * n > t)
return acc;
if (is_factor(t, n)){
if (is_prime(n, 3, true))
return gpf(t, n+2, n);
else
return gpf(t, n+2, acc);
}
else
return gpf(t, n+2, acc);
}


int main(int argc, char ** argv){
printf("%d\n", gpf(600851475143, 3, 0));
return 0;
}

该解决方案由三个函数组成。一个测试候选者是否是一个因子，另一个测试该因子是否是质数，最后一个将这两个组合在一起。

这里的一些关键想法是：

1-在SQRT停止递归（600851475143）

2-仅测试奇数的因子性

3-仅测试奇数素性的候选因子

求一个数的最大素因子的算法

C语言中的递归