<p>What is the best approach to calculating the largest prime factor of a number?</p>

<p>I'm thinking the most efficient would be the following:</p>

<ol>
<li>Find lowest prime number that divides cleanly</li>
<li>Check if result of division is prime</li>
<li>If not, find next lowest</li>
<li>Go to 2.</li>
</ol>

<p>I'm basing this assumption on it being easier to calculate the small prime factors. Is this about right? What other approaches should I look into?</p>

<p>Edit: I've now realised that my approach is futile if there are more than 2 prime factors in play, since step 2 fails when the result is a product of two other primes, therefore a recursive algorithm is needed.</p>

<p>Edit again: And now I've realised that this does still work, because the last found prime number has to be the highest one, therefore any further testing of the non-prime result from step 2 would result in a smaller prime.</p>

[{'answer_id': 23333, 'author': 'Klesk', 'author_id': 1516, 'author_profile': 'https://Stackoverflow.com/users/1516', 'pm_score': -1, 'selected': False, 'text': '<p>I think it would be good to store somewhere all possible primes smaller then n and just iterate through them to find the biggest divisior. You can get primes from <a href="http://www.prime-numbers.org/" rel="nofollow noreferrer">prime-numbers.org</a>.</p>\n\n<p>Of course I assume that your number isn\'t too big :)</p>\n'}, {'answer_id': 31235, 'author': 'palotasb', 'author_id': 3063, 'author_profile': 'https://Stackoverflow.com/users/3063', 'pm_score': -1, 'selected': False, 'text': "<p>This is probably not always faster but more optimistic about that you find a big prime divisor:</p>\n\n<ol>\n<li><code>N</code> is your number</li>\n<li>If it is prime then <code>return(N)</code></li>\n<li>Calculate primes up until <code>Sqrt(N)</code></li>\n<li>Go through the primes in descending order (largest first)\n\n<ul>\n<li>If <code>N is divisible by Prime</code> then <code>Return(Prime)</code></li>\n</ul></li>\n</ol>\n\n<p>Edit: In step 3 you can use the Sieve of Eratosthenes or Sieve of Atkins or whatever you like, but by itself the sieve won't find you the biggest prime factor. (Thats why I wouldn't choose SQLMenace's post as an official answer...)</p>\n"}, {'answer_id': 202429, 'author': 'Ralph M. Rickenbach', 'author_id': 4549416, 'author_profile': 'https://Stackoverflow.com/users/4549416', 'pm_score': 2, 'selected': False, 'text': '<pre class="lang-c prettyprint-override"><code>n = abs(number);\nresult = 1;\nif (n mod 2 == 0) {\n result = 2;\n while (n mod 2 = 0) n /= 2;\n}\nfor(i=3; i&lt;sqrt(n); i+=2) {\n if (n mod i == 0) {\n   result = i;\n   while (n mod i = 0)  n /= i;\n }\n}\nreturn max(n,result)\n</code></pre>\n<p>There are some modulo tests that are superflous, as n can never be divided by 6 if all factors 2 and 3 have been removed. You could only allow primes for i, which is shown in several other answers here.</p>\n<p>You could actually intertwine the sieve of Eratosthenes here:</p>\n<ul>\n<li>First create the list of integers up\nto <code>sqrt(n)</code>.</li>\n<li>In the for loop mark all multiples\nof i up to the new <code>sqrt(n)</code> as not\nprime, and use a while loop instead.</li>\n<li>set i to the next prime number in\nthe list.</li>\n</ul>\n<p>Also see <a href="https://stackoverflow.com/questions/201374/project-euler-question-3-help">this question</a>.</p>\n'}, {'answer_id': 242189, 'author': 'Artelius', 'author_id': 31945, 'author_profile': 'https://Stackoverflow.com/users/31945', 'pm_score': 8, 'selected': True, 'text': '<p>Actually there are several more efficient ways to find factors of big numbers (for smaller ones trial division works reasonably well). </p>\n\n<p>One method which is very fast if the input number has two factors very close to its square root is known as <a href="http://en.wikipedia.org/wiki/Fermat&#39;s_factorization_method" rel="noreferrer">Fermat factorisation</a>. It makes use of the identity N = (a + b)(a - b) = a^2 - b^2 and is easy to understand and implement. Unfortunately it\'s not very fast in general.</p>\n\n<p>The best known method for factoring numbers up to 100 digits long is the <a href="http://en.wikipedia.org/wiki/Quadratic_sieve" rel="noreferrer">Quadratic sieve</a>. As a bonus, part of the algorithm is easily done with parallel processing.</p>\n\n<p>Yet another algorithm I\'ve heard of is <a href="http://en.wikipedia.org/wiki/Pollard&#39;s_rho_algorithm" rel="noreferrer">Pollard\'s Rho algorithm</a>. It\'s not as efficient as the Quadratic Sieve in general but seems to be easier to implement.</p>\n\n<hr>\n\n<p>Once you\'ve decided on how to split a number into two factors, here is the fastest algorithm I can think of to find the largest prime factor of a number:</p>\n\n<p>Create a priority queue which initially stores the number itself. Each iteration, you remove the highest number from the queue, and attempt to split it into two factors (not allowing 1 to be one of those factors, of course). If this step fails, the number is prime and you have your answer! Otherwise you add the two factors into the queue and repeat.</p>\n'}, {'answer_id': 242274, 'author': 'Apocalisp', 'author_id': 3434, 'author_profile': 'https://Stackoverflow.com/users/3434', 'pm_score': 2, 'selected': False, 'text': '\n\n<p>The simplest solution is a pair of <em>mutually recursive</em> functions.</p>\n\n<p>The first function generates all the prime numbers:</p>\n\n<ol>\n<li>Start with a list of all natural numbers greater than 1.</li>\n<li>Remove all numbers that are not prime. That is, numbers that have no prime factors (other than themselves). See below.</li>\n</ol>\n\n<p>The second function returns the prime factors of a given number <code>n</code> in increasing order.</p>\n\n<ol>\n<li>Take a list of all the primes (see above).</li>\n<li>Remove all the numbers that are not factors of <code>n</code>.</li>\n</ol>\n\n<p>The largest prime factor of <code>n</code> is the last number given by the second function.</p>\n\n<p>This algorithm requires a <em>lazy list</em> or a language (or data structure) with <em>call-by-need</em> semantics.</p>\n\n<p>For clarification, here is one (inefficient) implementation of the above in Haskell:</p>\n\n<pre class="lang-hs prettyprint-override"><code>import Control.Monad\n\n-- All the primes\nprimes = 2 : filter (ap (&lt;=) (head . primeFactors)) [3,5..]\n\n-- Gives the prime factors of its argument\nprimeFactors = factor primes\n  where factor [] n = []\n        factor xs@(p:ps) n =\n          if p*p &gt; n then [n]\n          else let (d,r) = divMod n p in\n            if r == 0 then p : factor xs d\n            else factor ps n\n\n-- Gives the largest prime factor of its argument\nlargestFactor = last . primeFactors\n</code></pre>\n\n<p>Making this faster is just a matter of being more clever about detecting which numbers are prime and/or factors of <code>n</code>, but the algorithm stays the same.</p>\n'}, {'answer_id': 242290, 'author': 'nickf', 'author_id': 9021, 'author_profile': 'https://Stackoverflow.com/users/9021', 'pm_score': 2, 'selected': False, 'text': "<p>All numbers can be expressed as the product of primes, eg:</p>\n\n<pre><code>102 = 2 x 3 x 17\n712 = 2 x 2 x 2 x 89\n</code></pre>\n\n<p>You can find these by simply starting at 2 and simply continuing to divide until the result isn't a multiple of your number:</p>\n\n<pre><code>712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1\n</code></pre>\n\n<p>using this method you don't have to actually calculate any primes: they'll all be primes, based on the fact that you've already factorised the number as much as possible with all preceding numbers.</p>\n\n<pre><code>number = 712;\ncurrNum = number;    // the value we'll actually be working with\nfor (currFactor in 2 .. number) {\n    while (currNum % currFactor == 0) {\n        // keep on dividing by this number until we can divide no more!\n        currNum = currNum / currFactor     // reduce the currNum\n    }\n    if (currNum == 1) return currFactor;    // once it hits 1, we're done.\n}\n</code></pre>\n"}, {'answer_id': 242331, 'author': 'Loren Pechtel', 'author_id': 10659, 'author_profile': 'https://Stackoverflow.com/users/10659', 'pm_score': -1, 'selected': False, 'text': "<p>It seems to me that step #2 of the algorithm given isn't going to be all that efficient an approach.  You have no reasonable expectation that it is prime.</p>\n\n<p>Also, the previous answer suggesting the Sieve of Eratosthenes is utterly wrong.  I just wrote two programs to factor 123456789.  One was based on the Sieve, one was based on the following:</p>\n\n<pre><code>1)  Test = 2 \n2)  Current = Number to test \n3)  If Current Mod Test = 0 then  \n3a)     Current = Current Div Test \n3b)     Largest = Test\n3c)     Goto 3. \n4)  Inc(Test) \n5)  If Current &lt; Test goto 4\n6)  Return Largest\n</code></pre>\n\n<p>This version was 90x faster than the Sieve.</p>\n\n<p>The thing is, on modern processors the type of operation matters far less than the number of operations, not to mention that the algorithm above can run in cache, the Sieve can't.  The Sieve uses a lot of operations striking out all the composite numbers.</p>\n\n<p>Note, also, that my dividing out factors as they are identified reduces the space that must be tested.</p>\n"}, {'answer_id': 412942, 'author': 'Kenan Banks', 'author_id': 43089, 'author_profile': 'https://Stackoverflow.com/users/43089', 'pm_score': 7, 'selected': False, 'text': '<p>Here\'s the best algorithm I know of (in Python)</p>\n\n\n\n<pre class="lang-python prettyprint-override"><code>def prime_factors(n):\n    """Returns all the prime factors of a positive integer"""\n    factors = []\n    d = 2\n    while n &gt; 1:\n        while n % d == 0:\n            factors.append(d)\n            n /= d\n        d = d + 1\n\n    return factors\n\n\npfs = prime_factors(1000)\nlargest_prime_factor = max(pfs) # The largest element in the prime factor list\n</code></pre>\n\n<p>The above method runs in <code>O(n)</code> in the worst case (when the input is a prime number).</p>\n\n<p><strong>EDIT:</strong><br>\nBelow is the <code>O(sqrt(n))</code> version, as suggested in the comment. Here is the code, once more.</p>\n\n<pre class="lang-python prettyprint-override"><code>def prime_factors(n):\n    """Returns all the prime factors of a positive integer"""\n    factors = []\n    d = 2\n    while n &gt; 1:\n        while n % d == 0:\n            factors.append(d)\n            n /= d\n        d = d + 1\n        if d*d &gt; n:\n            if n &gt; 1: factors.append(n)\n            break\n    return factors\n\n\npfs = prime_factors(1000)\nlargest_prime_factor = max(pfs) # The largest element in the prime factor list\n</code></pre>\n'}, {'answer_id': 830001, 'author': 'Sundar R', 'author_id': 8127, 'author_profile': 'https://Stackoverflow.com/users/8127', 'pm_score': 4, 'selected': False, 'text': '<p>My answer is based on <a href="https://stackoverflow.com/questions/23287/prime-factors/412942#412942">Triptych</a>\'s, but improves a lot on it. It is based on the fact that beyond 2 and 3, all the prime numbers are of the form 6n-1 or 6n+1. </p>\n\n<pre><code>var largestPrimeFactor;\nif(n mod 2 == 0)\n{\n    largestPrimeFactor = 2;\n    n = n / 2 while(n mod 2 == 0);\n}\nif(n mod 3 == 0)\n{\n    largestPrimeFactor = 3;\n    n = n / 3 while(n mod 3 == 0);\n}\n\nmultOfSix = 6;\nwhile(multOfSix - 1 &lt;= n)\n{\n    if(n mod (multOfSix - 1) == 0)\n    {\n        largestPrimeFactor = multOfSix - 1;\n        n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);\n    }\n\n    if(n mod (multOfSix + 1) == 0)\n    {\n        largestPrimeFactor = multOfSix + 1;\n        n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);\n    }\n    multOfSix += 6;\n}\n</code></pre>\n\n<p>I recently wrote a <a href="http://thetaoishere.blogspot.com/2009/04/finding-largest-prime-factor.html" rel="nofollow noreferrer">blog article</a> explaining how this algorithm works. </p>\n\n<p>I would venture that a method in which there is no need for a test for primality (and no sieve construction) would run faster than one which does use those. If that is the case, this is probably the fastest algorithm here. </p>\n'}, {'answer_id': 7698513, 'author': 'Chitransh', 'author_id': 985586, 'author_profile': 'https://Stackoverflow.com/users/985586', 'pm_score': -1, 'selected': False, 'text': '<pre><code>#include&lt;stdio.h&gt;\n#include&lt;conio.h&gt;\n#include&lt;math.h&gt;\n#include &lt;time.h&gt;\n\nfactor(long int n)\n{\nlong int i,j;\nwhile(n&gt;=4)\n {\nif(n%2==0) {  n=n/2;   i=2;   }\n\n else\n { i=3;\nj=0;\n  while(j==0)\n  {\n   if(n%i==0)\n   {j=1;\n   n=n/i;\n   }\n   i=i+2;\n  }\n i-=2;\n }\n }\nreturn i;\n }\n\n void main()\n { \n  clock_t start = clock();\n  long int n,sp;\n  clrscr();\n  printf("enter value of n");\n  scanf("%ld",&amp;n);\n  sp=factor(n);\n  printf("largest prime factor is %ld",sp);\n\n  printf("Time elapsed: %f\\n", ((double)clock() - start) / CLOCKS_PER_SEC);\n  getch();\n }\n</code></pre>\n'}, {'answer_id': 9473540, 'author': 'thejosh', 'author_id': 1236662, 'author_profile': 'https://Stackoverflow.com/users/1236662', 'pm_score': 2, 'selected': False, 'text': "<p>I'm aware this is not a fast solution. Posting as hopefully easier to understand slow solution.</p>\n\n<pre><code> public static long largestPrimeFactor(long n) {\n\n        // largest composite factor must be smaller than sqrt\n        long sqrt = (long)Math.ceil(Math.sqrt((double)n));\n\n        long largest = -1;\n\n        for(long i = 2; i &lt;= sqrt; i++) {\n            if(n % i == 0) {\n                long test = largestPrimeFactor(n/i);\n                if(test &gt; largest) {\n                    largest = test;\n                }\n            }\n        }\n\n        if(largest != -1) {\n            return largest;\n        }\n\n        // number is prime\n        return n;\n    } \n</code></pre>\n"}, {'answer_id': 16595283, 'author': 'pedram', 'author_id': 1615031, 'author_profile': 'https://Stackoverflow.com/users/1615031', 'pm_score': -1, 'selected': False, 'text': '<p>Here is the same function@Triptych provided as a generator, which has also been simplified slightly. </p>\n\n<pre><code>def primes(n):\n    d = 2\n    while (n &gt; 1):\n        while (n%d==0):\n            yield d\n            n /= d\n        d += 1\n</code></pre>\n\n<p>the max prime can then be found using:</p>\n\n<pre><code>n= 373764623\nmax(primes(n))\n</code></pre>\n\n<p>and a list of factors found using:</p>\n\n<pre><code>list(primes(n))\n</code></pre>\n'}, {'answer_id': 19848596, 'author': 'guoger', 'author_id': 2337174, 'author_profile': 'https://Stackoverflow.com/users/2337174', 'pm_score': -1, 'selected': False, 'text': '<p>Compute a list storing prime numbers first, e.g. 2 3 5 7 11 13 ...</p>\n\n<p>Every time you prime factorize a number, use implementation by Triptych but iterating this list of prime numbers rather than natural integers.</p>\n'}, {'answer_id': 21238400, 'author': 'Seamus Barrett', 'author_id': 1297920, 'author_profile': 'https://Stackoverflow.com/users/1297920', 'pm_score': 0, 'selected': False, 'text': "<p>Here is my attempt in c#. The last print out is the largest prime factor of the number. I checked and it works.</p>\n\n<pre><code>namespace Problem_Prime\n{\n  class Program\n  {\n    static void Main(string[] args)\n    {\n      /*\n       The prime factors of 13195 are 5, 7, 13 and 29.\n\n      What is the largest prime factor of the number 600851475143 ?\n       */\n      long x = 600851475143;\n      long y = 2;\n      while (y &lt; x)\n      {\n        if (x % y == 0)\n        {\n          // y is a factor of x, but is it prime\n          if (IsPrime(y))\n          {\n            Console.WriteLine(y);\n          }\n          x /= y;\n        }\n\n        y++;\n\n      }\n      Console.WriteLine(y);\n      Console.ReadLine();\n    }\n    static bool IsPrime(long number)\n    {\n      //check for evenness\n      if (number % 2 == 0)\n      {\n        if (number == 2)\n        {\n          return true;\n        }\n        return false;\n      }\n      //don't need to check past the square root\n      long max = (long)Math.Sqrt(number);\n      for (int i = 3; i &lt;= max; i += 2)\n      {\n        if ((number % i) == 0)\n        {\n          return false;\n        }\n      }\n      return true;\n    }\n\n  }\n}\n</code></pre>\n"}, {'answer_id': 22723233, 'author': 'Paul Vargas', 'author_id': 870248, 'author_profile': 'https://Stackoverflow.com/users/870248', 'pm_score': -1, 'selected': False, 'text': '<p>With Java:</p>\n\n<p>For <code>int</code> values:</p>\n\n<pre><code>public static int[] primeFactors(int value) {\n    int[] a = new int[31];\n    int i = 0, j;\n    int num = value;\n    while (num % 2 == 0) {\n        a[i++] = 2;\n        num /= 2;\n    }\n    j = 3;\n    while (j &lt;= Math.sqrt(num) + 1) {\n        if (num % j == 0) {\n            a[i++] = j;\n            num /= j;\n        } else {\n            j += 2;\n        }\n    }\n    if (num &gt; 1) {\n        a[i++] = num;\n    }\n    int[] b = Arrays.copyOf(a, i);\n    return b;\n}\n</code></pre>\n\n<p>For <code>long</code> values:</p>\n\n<pre><code>static long[] getFactors(long value) {\n    long[] a = new long[63];\n    int i = 0;\n    long num = value;\n    while (num % 2 == 0) {\n        a[i++] = 2;\n        num /= 2;\n    }\n    long j = 3;\n    while (j &lt;= Math.sqrt(num) + 1) {\n        if (num % j == 0) {\n            a[i++] = j;\n            num /= j;\n        } else {\n            j += 2;\n        }\n    }\n    if (num &gt; 1) {\n        a[i++] = num;\n    }\n    long[] b = Arrays.copyOf(a, i);\n    return b;\n}\n</code></pre>\n'}, {'answer_id': 23013770, 'author': 'the_prole', 'author_id': 2715384, 'author_profile': 'https://Stackoverflow.com/users/2715384', 'pm_score': 2, 'selected': False, 'text': "<pre><code>    //this method skips unnecessary trial divisions and makes \n    //trial division more feasible for finding large primes\n\n    public static void main(String[] args) \n    {\n        long n= 1000000000039L; //this is a large prime number \n        long i = 2L;\n        int test = 0;\n\n        while (n &gt; 1)\n        {\n            while (n % i == 0)\n            {\n                n /= i;     \n            }\n\n            i++;\n\n            if(i*i &gt; n &amp;&amp; n &gt; 1) \n            {\n                System.out.println(n); //prints n if it's prime\n                test = 1;\n                break;\n            }\n        }\n\n        if (test == 0)  \n            System.out.println(i-1); //prints n if it's the largest prime factor\n    }\n</code></pre>\n"}, {'answer_id': 23974478, 'author': 'Rishabh Prasad', 'author_id': 3695673, 'author_profile': 'https://Stackoverflow.com/users/3695673', 'pm_score': 0, 'selected': False, 'text': '<pre><code>#python implementation\nimport math\nn = 600851475143\ni = 2\nfactors=set([])\nwhile i&lt;math.sqrt(n):\n   while n%i==0:\n       n=n/i\n       factors.add(i)\n   i+=1\nfactors.add(n)\nlargest=max(factors)\nprint factors\nprint largest\n</code></pre>\n'}, {'answer_id': 24714465, 'author': '4aRk Kn1gh7', 'author_id': 3736555, 'author_profile': 'https://Stackoverflow.com/users/3736555', 'pm_score': 0, 'selected': False, 'text': '<p>Calculates the largest prime factor of a number using recursion in C++. The working of the code is explained below:</p>\n\n<pre><code>int getLargestPrime(int number) {\n    int factor = number; // assumes that the largest prime factor is the number itself\n    for (int i = 2; (i*i) &lt;= number; i++) { // iterates to the square root of the number till it finds the first(smallest) factor\n        if (number % i == 0) { // checks if the current number(i) is a factor\n            factor = max(i, number / i); // stores the larger number among the factors\n            break; // breaks the loop on when a factor is found\n        }\n    }\n    if (factor == number) // base case of recursion\n        return number;\n    return getLargestPrime(factor); // recursively calls itself\n}\n</code></pre>\n'}, {'answer_id': 33609588, 'author': 'Jyothir Aditya Singh', 'author_id': 4037878, 'author_profile': 'https://Stackoverflow.com/users/4037878', 'pm_score': 1, 'selected': False, 'text': '<p>Python Iterative approach by removing all prime factors from the number</p>\n\n<pre><code>def primef(n):\n    if n &lt;= 3:\n        return n\n    if n % 2 == 0:\n        return primef(n/2)\n    elif n % 3 ==0:\n        return primef(n/3)\n    else:\n        for i in range(5, int((n)**0.5) + 1, 6):\n            #print i\n            if n % i == 0:\n                return primef(n/i)\n            if n % (i + 2) == 0:\n                return primef(n/(i+2))\n    return n\n</code></pre>\n'}, {'answer_id': 33854720, 'author': 'penkovsky', 'author_id': 558254, 'author_profile': 'https://Stackoverflow.com/users/558254', 'pm_score': 0, 'selected': False, 'text': "<p>Here is my approach to quickly calculate the largest prime factor.\nIt is based on fact that modified <code>x</code> does not contain non-prime factors. To achieve that, we divide <code>x</code> as soon as a factor is found. Then, the only thing left is to return the largest factor. It would be already prime.</p>\n\n<p>The code (Haskell):</p>\n\n<pre><code>f max' x i | i &gt; x = max'\n           | x `rem` i == 0 = f i (x `div` i) i  -- Divide x by its factor\n           | otherwise = f max' x (i + 1)  -- Check for the next possible factor\n\ng x = f 2 x 2\n</code></pre>\n"}, {'answer_id': 36360681, 'author': 'Vlad Bezden', 'author_id': 30038, 'author_profile': 'https://Stackoverflow.com/users/30038', 'pm_score': 3, 'selected': False, 'text': '<p>JavaScript code:</p>\n\n<pre><code>\'option strict\';\n\nfunction largestPrimeFactor(val, divisor = 2) { \n    let square = (val) =&gt; Math.pow(val, 2);\n\n    while ((val % divisor) != 0 &amp;&amp; square(divisor) &lt;= val) {\n        divisor++;\n    }\n\n    return square(divisor) &lt;= val\n        ? largestPrimeFactor(val / divisor, divisor)\n        : val;\n}\n</code></pre>\n\n<p>Usage Example:</p>\n\n<pre><code>let result = largestPrimeFactor(600851475143);\n</code></pre>\n\n<p><a href="https://codepen.io/vlad-bezden/pen/bpoqod/" rel="noreferrer">Here is an example of the code</a>:</p>\n'}, {'answer_id': 37829365, 'author': 's.n', 'author_id': 6195963, 'author_profile': 'https://Stackoverflow.com/users/6195963', 'pm_score': 0, 'selected': False, 'text': '<p>The following C++ algorithm is not the best one, but it works for numbers under a billion and its pretty fast</p>\n\n<pre><code>#include &lt;iostream&gt;\nusing namespace std;\n\n// ------ is_prime ------\n// Determines if the integer accepted is prime or not\nbool is_prime(int n){\n    int i,count=0;\n    if(n==1 || n==2)\n      return true;\n    if(n%2==0)\n      return false;\n    for(i=1;i&lt;=n;i++){\n    if(n%i==0)\n        count++;\n    }\n    if(count==2)\n      return true;\n    else\n      return false;\n }\n // ------ nextPrime -------\n // Finds and returns the next prime number\n int nextPrime(int prime){\n     bool a = false;\n     while (a == false){\n         prime++;\n         if (is_prime(prime))\n            a = true;\n     }\n  return prime;\n }\n // ----- M A I N ------\n int main(){\n\n      int value = 13195;\n      int prime = 2;\n      bool done = false;\n\n      while (done == false){\n          if (value%prime == 0){\n             value = value/prime;\n             if (is_prime(value)){\n                 done = true;\n             }\n          } else {\n             prime = nextPrime(prime);\n          }\n      }\n        cout &lt;&lt; "Largest prime factor: " &lt;&lt; value &lt;&lt; endl;\n }\n</code></pre>\n'}, {'answer_id': 39263813, 'author': 'Kalpesh Dusane', 'author_id': 6742808, 'author_profile': 'https://Stackoverflow.com/users/6742808', 'pm_score': 1, 'selected': False, 'text': "<p>I am using algorithm which continues dividing the number by it's current Prime Factor.</p>\n\n<p>My Solution in python 3 :</p>\n\n<pre><code>def PrimeFactor(n):\n    m = n\n    while n%2==0:\n        n = n//2\n    if n == 1:         # check if only 2 is largest Prime Factor \n        return 2\n    i = 3\n    sqrt = int(m**(0.5))  # loop till square root of number\n    last = 0              # to store last prime Factor i.e. Largest Prime Factor\n    while i &lt;= sqrt :\n        while n%i == 0:\n            n = n//i       # reduce the number by dividing it by it's Prime Factor\n            last = i\n        i+=2\n    if n&gt; last:            # the remaining number(n) is also Factor of number \n        return n\n    else:\n        return last\nprint(PrimeFactor(int(input()))) \n</code></pre>\n\n<p>Input : <code>10</code>\nOutput : <code>5</code></p>\n\n<p>Input : <code>600851475143</code> \nOutput : <code>6857</code></p>\n"}, {'answer_id': 48862397, 'author': 'Ugnius Malūkas', 'author_id': 2122457, 'author_profile': 'https://Stackoverflow.com/users/2122457', 'pm_score': 3, 'selected': False, 'text': '<p>Similar to @Triptych answer but also different. In this example list or dictionary is not used. Code is written in Ruby</p>\n\n<pre class="lang-rb prettyprint-override"><code>def largest_prime_factor(number)\n  i = 2\n  while number &gt; 1\n    if number % i == 0\n      number /= i;\n    else\n      i += 1\n    end\n  end\n  return i\nend\n\nlargest_prime_factor(600851475143)\n# =&gt; 6857\n</code></pre>\n'}, {'answer_id': 51410864, 'author': 'Babar-Baig', 'author_id': 2293300, 'author_profile': 'https://Stackoverflow.com/users/2293300', 'pm_score': 0, 'selected': False, 'text': '<p>Found this solution on the web by "James Wang"</p>\n\n<pre><code>public static int getLargestPrime( int number) {\n\n    if (number &lt;= 1) return -1;\n\n    for (int i = number - 1; i &gt; 1; i--) {\n        if (number % i == 0) {\n            number = i;\n        }\n    }\n    return number;\n}\n</code></pre>\n'}, {'answer_id': 52311990, 'author': 'rashedcs', 'author_id': 6714430, 'author_profile': 'https://Stackoverflow.com/users/6714430', 'pm_score': 0, 'selected': False, 'text': '<p><strong>Prime factor using sieve :</strong> </p>\n\n<pre><code>#include &lt;bits/stdc++.h&gt;\nusing namespace std;\n#define N 10001  \ntypedef long long ll;\nbool visit[N];\nvector&lt;int&gt; prime;\n\nvoid sieve()\n{\n            memset( visit , 0 , sizeof(visit));\n            for( int i=2;i&lt;N;i++ )\n            {\n                if( visit[i] == 0)\n                {\n                    prime.push_back(i);\n                    for( int j=i*2; j&lt;N; j=j+i )\n                    {\n                        visit[j] = 1;\n                    }\n                }\n            }   \n}\nvoid sol(long long n, vector&lt;int&gt;&amp;prime)\n{\n            ll ans = n;\n            for(int i=0; i&lt;prime.size() || prime[i]&gt;n; i++)\n            {\n                while(n%prime[i]==0)\n                {\n                    n=n/prime[i];\n                    ans = prime[i];\n                }\n            }\n            ans = max(ans, n);\n            cout&lt;&lt;ans&lt;&lt;endl;\n}\nint main() \n{\n           ll tc, n;\n           sieve();\n\n           cin&gt;&gt;n;\n           sol(n, prime);\n\n           return 0;\n}\n</code></pre>\n'}, {'answer_id': 66403796, 'author': 'Vikas Gautam', 'author_id': 4850220, 'author_profile': 'https://Stackoverflow.com/users/4850220', 'pm_score': 0, 'selected': False, 'text': '<p>Here is my attempt in Clojure. Only walking the odds for <code>prime?</code> and the primes for prime factors ie. <code>sieve</code>. Using lazy sequences help producing the values just before they are needed.</p>\n<pre class="lang-clj prettyprint-override"><code>(defn prime? \n  ([n]\n    (let [oddNums (iterate #(+ % 2) 3)]\n    (prime? n (cons 2 oddNums))))\n  ([n [i &amp; is]]\n    (let [q (quot n i)\n          r (mod n i)]\n    (cond (&lt; n 2)       false\n          (zero? r)     false\n          (&gt; (* i i) n) true\n          :else         (recur n is)))))\n\n(def primes \n  (let [oddNums (iterate #(+ % 2) 3)]\n  (lazy-seq (cons 2 (filter prime? oddNums)))))\n\n;; Sieve of Eratosthenes\n(defn sieve\n  ([n] \n    (sieve primes n))\n  ([[i &amp; is :as ps] n]\n    (let [q (quot n i)\n          r (mod n i)]\n    (cond (&lt; n 2)       nil\n          (zero? r)     (lazy-seq (cons i (sieve ps q)))\n          (&gt; (* i i) n) (when (&gt; n 1) (lazy-seq [n]))\n          :else         (recur is n)))))\n\n(defn max-prime-factor [n]\n  (last (sieve n)))\n</code></pre>\n'}, {'answer_id': 66934492, 'author': 'Sam Ginrich', 'author_id': 9437799, 'author_profile': 'https://Stackoverflow.com/users/9437799', 'pm_score': 0, 'selected': False, 'text': "<p>Guess, there is no immediate way but performing a factorization, as examples above have done, i.e.</p>\n<p>in a iteration you identify a &quot;small&quot; factor <em>f</em> of a number <em>N</em>, then continue with the reduced problem &quot;find largest prime factor of <em>N':=N/f</em> with factor candidates <em>&gt;=f</em> &quot;.</p>\n<p>From certain size of <em>f</em> the expected search time is less, if you do a primality test on reduced <em>N'</em>, which in case confirms, that your <em>N'</em> is already the largest prime factor of initial <em>N</em>.</p>\n"}, {'answer_id': 68996148, 'author': 'Arty', 'author_id': 941531, 'author_profile': 'https://Stackoverflow.com/users/941531', 'pm_score': 1, 'selected': False, 'text': '<p>Inspired by your question I decided to implement my own version of factorization (and finding largest prime factor) in Python.</p>\n<p>Probably the simplest to implement, yet quite efficient, factoring algorithm that I know is <a href="https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm" rel="nofollow noreferrer">Pollard\'s Rho</a> algorithm. It has a running time of <code>O(N^(1/4))</code> at most which is much more faster than time of <code>O(N^(1/2))</code> for trial division algorithm. Both algos have these running times only in case of composite (non-prime) number, that\'s why primality test should be used to filter out prime (non-factorable) numbers.</p>\n<p>I used following algorithms in my code: <a href="https://en.wikipedia.org/wiki/Fermat_primality_test" rel="nofollow noreferrer">Fermat Primality Test</a> ...,    <a href="https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm" rel="nofollow noreferrer">Pollard\'s Rho Algorithm</a> ...,    <a href="https://en.wikipedia.org/wiki/Trial_division" rel="nofollow noreferrer">Trial Division Algorithm</a>. Fermat primality test is used before running Pollard\'s Rho in order to filter out prime numbers. Trial Division is used as a fallback because Pollard\'s Rho in very rare cases may fail to find a factor, especially for some small numbers.</p>\n<p>Obviously after fully factorizing a number into sorted list of prime factors the largest prime factor will be the last element in this list. In general case (for any random number) I don\'t know of any other ways to find out largest prime factor besides fully factorizing a number.</p>\n<p>As an example in my code I\'m factoring first <strong>190</strong> fractional digits of Pi, code factorizes this number within 1 second, and shows largest prime factor which is <strong>165</strong> digits (545 bits) in size!</p>\n<p><a href="https://tio.run/##lVZNb9s4EL37V8xi0bXUKrZIfQdNgD1sT4URLHILAkKOKJtbiVIpZh2j6G/PDiU5lOK06ApIZFGcNzNv5g3VHvW@kcHzc8FLEB0ruapzzVrVbPNtxfGHqLkjPXjvgVYirzq4goC6lwvA63fYa912l@s1l6uD@CJaXoh81ajd2jytP53QRJ1XQh@Z5p3uLUXdNkqDymXR1MNKCRI@XgGJB2xzKa4flcR1IcGhHgQeRB4kHhCCf4HbbywbBcLsQLAdd4YoXQuCwG1zcAZXK3MTUhs0CRdA3eGOeNKF39C9NZxE8Akh@WKycKse@WJhSGubqspVwdS@YWX@oBvlbOZ0kfgX6boZoN7RpOvh8mrXKKH39TllHiCx@5f8//lZ/h50Ot9xD44ePGE8vgeYPWb8ihJc2fSUvJge9qLifa6vWEEU43@1eyhMtk9odnRnW5B19Qaf5toqnn95vVnA1dUQ57nBEd09na32m@GjaZnZO5Oi8wTv8ccHIC68g83cGXyYmpwC3bxZ@DtlSFmvQd1Py3@3ucdqjvW6@HvfQJkjVcXQEn0JWCH@FZ1o5KkrBhFVohYaI9w0kv9iW9zO4Iaam766G0IaiiThDyCGQ9/mUXarvG25LJxJTSVcX5/yL4yYJyAFslYYEUrAnhhjFV0fLGCb9e/6Vevkq9e3A4ZXN4VJsnDn3M5jmsdVzJtGItDXlxWOmpsbFqZ01I6L62l7WVTpTmtVdkNVTmUYWX@ZN2fjZuRV/GwguudW8t6W5ocdcCo/wcYFMpYFPVVcOmXnApaGnkF3qHte4Pu7ywtyj1094uECPruu9fvGMJL/y8cdJ/1A4b6ZKIjZP5D@YcDjvns/4/cHuboD6wWvG@dE@TDBNDI4mV9D@2P3Hw6HVT9VHpp6rQ3b3fqhkahzqbt1K1Z7XY8WrTCduxqfzEVCEmU0joII0izJAhqkYQw0DoMgDWiSQeTTNA1JlhCIsyDLgiQiPkQp9bMkzMIQ0Dzwk5TEIfgxTWPqp1kGeE/9IExpBEFICUn8OMkmflNKwtRP44jgsZgiQhyHCfgZug9jP4vQL/qgAUkoYHBZ6KeEphCmBLFCDAowKJ8mPskCSCP04EdRlEGM5pRmYYqRh1ngBynJ4tGvkUkpVKeBZD6UChlH5vMKRbgTuoOmhBuxOAlqyg2z3DDLDbPcMMsNs9wwyw2z3DDLDbPcMMsIs4wwywizjDDLCLOMMMsIs4wwy0ifGgoRz6zl5rHecnW5NOd3v663Rn/YYivzz5mIYy6I0f7PqoIbo2k8483rzkChSqZ7Pudqhx8us339tqXzrW/YqtnRkxovVz4tv8MWC@HBN6O5Tlupfh9r5PZe@rWpp1vj4K8qbzteGA@qecR5NskGD1q9xQ8h/GxZdvxhiSpDZTMm85ozZmbtkrE6F5Kx5SC6QYCL5@f/AA" rel="nofollow noreferrer" title="Python 3 – Try It Online">Try it online!</a></p>\n<pre class="lang-py prettyprint-override"><code>def is_fermat_probable_prime(n, *, trials = 32):\n    # https://en.wikipedia.org/wiki/Fermat_primality_test\n    import random\n    if n &lt;= 16:\n        return n in (2, 3, 5, 7, 11, 13)\n    for i in range(trials):\n        if pow(random.randint(2, n - 2), n - 1, n) != 1:\n            return False\n    return True\n\ndef pollard_rho_factor(N, *, trials = 16):\n    # https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm\n    import random, math\n    for j in range(trials):\n        i, stage, y, x = 0, 2, 1, random.randint(1, N - 2)\n        while True:\n            r = math.gcd(N, x - y)\n            if r != 1:\n                break\n            if i == stage:\n                y = x\n                stage &lt;&lt;= 1\n            x = (x * x + 1) % N\n            i += 1\n        if r != N:\n            return [r, N // r]\n    return [N] # Pollard-Rho failed\n\ndef trial_division_factor(n, *, limit = None):\n    # https://en.wikipedia.org/wiki/Trial_division\n    fs = []\n    while n &amp; 1 == 0:\n        fs.append(2)\n        n &gt;&gt;= 1\n    d = 3\n    while d * d &lt;= n and limit is None or d &lt;= limit:\n        q, r = divmod(n, d)\n        if r == 0:\n            fs.append(d)\n            n = q\n        else:\n            d += 2\n    if n &gt; 1:\n        fs.append(n)\n    return fs\n\ndef factor(n):\n    if n &lt;= 1:\n        return []\n    if is_fermat_probable_prime(n):\n        return [n]\n    fs = trial_division_factor(n, limit = 1 &lt;&lt; 12)\n    if len(fs) &gt;= 2:\n        return sorted(fs[:-1] + factor(fs[-1]))\n    fs = pollard_rho_factor(n)\n    if len(fs) &gt;= 2:\n        return sorted([e1 for e0 in fs for e1 in factor(e0)])\n    return trial_division_factor(n)\n\ndef demo():\n    import time, math\n    # http://www.math.com/tables/constants/pi.htm\n    # pi = 3.\n    #     1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679\n    #     8214808651 3282306647 0938446095 5058223172 5359408128 4811174502 8410270193 8521105559 6446229489 5493038196\n    # n = first 190 fractional digits of Pi\n    n =   1415926535_8979323846_2643383279_5028841971_6939937510_5820974944_5923078164_0628620899_8628034825_3421170679_8214808651_3282306647_0938446095_5058223172_5359408128_4811174502_8410270193_8521105559_6446229489\n    print(\'Number:\', n)\n    tb = time.time()\n    fs = factor(n)\n    print(\'All Prime Factors:\', fs)\n    print(\'Largest Prime Factor:\', f\'({math.log2(fs[-1]):.02f} bits, {len(str(fs[-1]))} digits)\', fs[-1])\n    print(\'Time Elapsed:\', round(time.time() - tb, 3), \'sec\')\n\nif __name__ == \'__main__\':\n    demo()\n</code></pre>\n<p>Output:</p>\n<pre><code>Number: 1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489\nAll Prime Factors: [3, 71, 1063541, 153422959, 332958319, 122356390229851897378935483485536580757336676443481705501726535578690975860555141829117483263572548187951860901335596150415443615382488933330968669408906073630300473]\nLargest Prime Factor: (545.09 bits, 165 digits) 122356390229851897378935483485536580757336676443481705501726535578690975860555141829117483263572548187951860901335596150415443615382488933330968669408906073630300473\nTime Elapsed: 0.593 sec\n</code></pre>\n'}, {'answer_id': 73180644, 'author': '4d30', 'author_id': 14868795, 'author_profile': 'https://Stackoverflow.com/users/14868795', 'pm_score': 0, 'selected': False, 'text': "<h1>Recursion in C</h1>\n<p>Algorithm could be</p>\n<ol>\n<li>Check if n is a factor or t</li>\n<li>Check if n is prime. If so, remember n</li>\n<li>Increment n</li>\n<li>Repeat until n &gt; sqrt(t)</li>\n</ol>\n<p>Here's an example of a (tail)recursive solution to the problem in C:</p>\n<pre><code>#include &lt;stdio.h&gt;\n#include &lt;stdbool.h&gt;\n\nbool is_factor(long int t, long int n){\n    return ( t%n == 0);\n}\n\nbool is_prime(long int n0, long int n1, bool acc){\n    if ( n1 * n1 &gt; n0 || acc &lt; 1 )\n        return acc;\n    else\n        return is_prime(n0, n1+2, acc &amp;&amp; (n0%n1 != 0));\n}\n\nint gpf(long int t, long int n, long int acc){\n    if (n * n &gt; t)\n        return acc;\n    if (is_factor(t, n)){\n        if (is_prime(n, 3, true))\n            return gpf(t, n+2, n);\n        else\n            return gpf(t, n+2, acc);\n    }\n    else\n        return gpf(t, n+2, acc);\n}\n\nint main(int argc, char ** argv){\n    printf(&quot;%d\\n&quot;, gpf(600851475143, 3, 0));\n    return 0;\n}\n</code></pre>\n<p>The solution is composed of three functions. One to test if the candidate is a factor, another to test if that factor is prime, and finally one to compose those two together.</p>\n<p>Some key ideas here are:</p>\n<p>1- Stopping the recursion at sqrt(600851475143)</p>\n<p>2- Only test odd numbers for factorness</p>\n<p>3- Only testing candidate factors for primeness with odd numbers</p>\n"}]
['https://Stackoverflow.com/questions/23287', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1951/']