求一个数的最大素因子-yiteyi-C++库

给定一个正整数’n’（1<=n<=10 ¹⁵ ).求一个数的最大素因子。

null

Input: 6Output: 3ExplanationPrime factor of 6 are- 2, 3Largest of them is '3'Input: 15Output: 5

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这种方法很简单，只需将给定的数除以一个数的除数进行因式分解，并不断更新最大素因子。看见这了解更多。

C++

                         // C++ Program to find largest prime                       
                         // factor of number                       
                         #include <iostream>                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // A function to find largest prime factor                       
                         long                                     long                                     maxPrimeFactors(                                     long                                     long                                     n)                       
                         {                       
                                                 // Initialize the maximum prime factor                       
                                                 // variable with the lowest one                       
                                                 long                                     long                                     maxPrime = -1;                       
           
                                                 // Print the number of 2s that divide n                       
                                                 while                                     (n % 2 == 0) {                       
                                                 maxPrime = 2;                       
                                                 n >>= 1;                                     // equivalent to n /= 2                       
                                                 }                       
                                                 // n must be odd at this point                       
                                                 while                                     (n % 3 == 0) {                       
                                                 maxPrime = 3;                       
                                                 n=n/3;                       
                                                 }                       
           
                                                 // now we have to iterate only for integers                       
                                                 // who does not have prime factor 2 and 3                       
                                                 for                                     (                                     int                                     i = 5; i <=                                     sqrt                                     (n); i += 6) {                       
                                                 while                                     (n % i == 0) {                       
                                                 maxPrime = i;                       
                                                 n = n / i;                       
                                                 }                       
                                                 while                                     (n % (i+2) == 0) {                       
                                                 maxPrime = i+2;                       
                                                 n = n / (i+2);                       
                                                 }                       
                                                 }                       
           
                                                 // This condition is to handle the case                       
                                                 // when n is a prime number greater than 4                       
                                                 if                                     (n > 4)                       
                                                 maxPrime = n;                       
           
                                                 return                                     maxPrime;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 long                                     long                                     n = 15;                       
                                                 cout << maxPrimeFactors(n) << endl;                       
           
                                                 n = 25698751364526;                       
                                                 cout <<  maxPrimeFactors(n);                       
           
                         }                       

C

                         // C Program to find largest prime                       
                         // factor of number                       
                         #include <math.h>                       
                         #include <stdio.h>                       
           
                         // A function to find largest prime factor                       
                         long                                     long                                     maxPrimeFactors(                                     long                                     long                                     n)                       
                         {                       
                                                 // Initialize the maximum prime factor                       
                                                 // variable with the lowest one                       
                                                 long                                     long                                     maxPrime = -1;                       
           
                                                 // Print the number of 2s that divide n                       
                                                 while                                     (n % 2 == 0) {                       
                                                 maxPrime = 2;                       
                                                 n >>= 1;                                     // equivalent to n /= 2                       
                                                 }                       
                                                 // n must be odd at this point                       
                                                 while                                     (n % 3 == 0) {                       
                                                 maxPrime = 3;                       
                                                 n = n / 3;                       
                                                 }                       
           
                                                 // now we have to iterate only for integers                       
                                                 // who does not have prime factor 2 and 3                       
                                                 for                                     (                                     int                                     i = 5; i <=                                     sqrt                                     (n); i += 6) {                       
                                                 while                                     (n % i == 0) {                       
                                                 maxPrime = i;                       
                                                 n = n / i;                       
                                                 }                       
                                                 while                                     (n % (i + 2) == 0) {                       
                                                 maxPrime = i + 2;                       
                                                 n = n / (i + 2);                       
                                                 }                       
                                                 }                       
           
                                                 // This condition is to handle the case                       
                                                 // when n is a prime number greater than 4                       
                                                 if                                     (n > 4)                       
                                                 maxPrime = n;                       
           
                                                 return                                     maxPrime;                       
                         }                       
           
                         // Driver program to test above function                       
                         int                                     main()                       
                         {                       
                                                 long                                     long                                     n = 15;                       
                                                 printf                                     (                                     "%lld"                                     , maxPrimeFactors(n));                       
           
                                                 n = 25698751364526;                       
                                                 printf                                     (                                     "%lld"                                     , maxPrimeFactors(n));                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Program to find largest                       
                         // prime factor of number                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
           
                                                 // function to find largest prime factor                       
                                                 static                                     long                                     maxPrimeFactors(                                     long                                     n)                       
                                                 {                       
                                                 // Initialize the maximum prime                       
                                                 // factor variable with the                       
                                                 // lowest one                       
                                                 long                                     maxPrime = -                                     1                                     ;                       
           
                                                 // Print the number of 2s                       
                                                 // that divide n                       
                                                 while                                     (n %                                     2                                     ==                                     0                                     ) {                       
                                                 maxPrime =                                     2                                     ;                       
           
                                                 // equivalent to n /= 2                       
                                                 n >>=                                     1                                     ;                       
                                                 }                       
                                                 // n must be odd at this point                       
                                                 while                                     (n %                                     3                                     ==                                     0                                     ) {                       
                                                 maxPrime =                                     3                                     ;                       
                                                 n = n /                                     3                                     ;                       
                                                 }                       
           
                                                 // now we have to iterate only for integers                       
                                                 // who does not have prime factor 2 and 3                       
                                                 for                                     (                                     int                                     i =                                     5                                     ; i <= Math.sqrt(n); i +=                                     6                                     ) {                       
                                                 while                                     (n % i ==                                     0                                     ) {                       
                                                 maxPrime = i;                       
                                                 n = n / i;                       
                                                 }                       
                                                 while                                     (n % (i +                                     2                                     ) ==                                     0                                     ) {                       
                                                 maxPrime = i +                                     2                                     ;                       
                                                 n = n / (i +                                     2                                     );                       
                                                 }                       
                                                 }                       
           
                                                 // This condition is to handle the case                       
                                                 // when n is a prime number greater than 4                       
                                                 if                                     (n >                                     4                                     )                       
                                                 maxPrime = n;                       
           
                                                 return                                     maxPrime;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 Long n = 15l;                       
                                                 System.out.println(maxPrimeFactors(n));                       
           
                                                 n = 25698751364526l;                       
                                                 System.out.println(maxPrimeFactors(n));                       
                                                 }                       
                         }                       

Python3

                         # Python3 code to find largest prime                       
                         # factor of number                       
                         import                                     math                       
           
                         # A function to find largest prime factor                       
                         def                                     maxPrimeFactors (n):                       
                                   
                                                 # Initialize the maximum prime factor                       
                                                 # variable with the lowest one                       
                                                 maxPrime                                     =                                     -                                     1                       
                                   
                                                 # Print the number of 2s that divide n                       
                                                 while                                     n                                     %                                     2                                     =                                     =                                     0                                     :                       
                                                 maxPrime                                     =                                     2                       
                                                 n >>                                     =                                     1                                     # equivalent to n /= 2                       
                                   
                                                 # n must be odd at this point                       
                                                 while                                     n                                     %                                     3                                     =                                     =                                     0                                     :                       
                                                 maxPrime                                     =                                     3                       
                                                 n                                     =                                     n                                     /                                     3                       
                                   
                                                 # now we have to iterate only for integers                       
                                                 # who does not have prime factor 2 and 3                       
                                                 for                                     i                                     in                                     range                                     (                                     5                                     ,                                     int                                     (math.sqrt(n))                                     +                                     1                                     ,                                     6                                     ):                       
                                                 while                                     n                                     %                                     i                                     =                                     =                                     0                                     :                       
                                                 maxPrime                                     =                                     i                       
                                                 n                                     =                                     n                                     /                                     i                       
                                                 while                                     n                                     %                                     (i                                     +                                     2                                     )                                     =                                     =                                     0                                     :                       
                                                 maxPrime                                     =                                     i                                     +                                     2                       
                                                 n                                     =                                     n                                     /                                     (i                                     +                                     2                                     )                       
                                   
                                                 # This condition is to handle the                       
                                                 # case when n is a prime number                       
                                                 # greater than 4                       
                                                 if                                     n >                                     4                                     :                       
                                                 maxPrime                                     =                                     n                       
                                   
                                                 return                                     int                                     (maxPrime)                       
           
                         # Driver code to test above function                       
                         n                                     =                                     15                       
                         print                                     (maxPrimeFactors(n))                       
           
                         n                                     =                                     25698751364526                       
                         print                                     (maxPrimeFactors(n))                       

C#

                         // C# program to find largest                       
                         // prime factor of number                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // function to find largest prime factor                       
                                                 static                                     long                                     maxPrimeFactors(                                     long                                     n)                       
                                                 {                       
                                                 // Initialize the maximum prime                       
                                                 // factor variable with the                       
                                                 // lowest one                       
                                                 long                                     maxPrime = -1;                       
           
                                                 // Print the number of 2s                       
                                                 // that divide n                       
                                                 while                                     (n % 2 == 0) {                       
                                                 maxPrime = 2;                       
           
                                                 // equivalent to n /= 2                       
                                                 n >>= 1;                       
                                                 }                       
                                                 // n must be odd at this point                       
                                                 while                                     (n % 3 == 0) {                       
                                                 maxPrime = 3;                       
                                                 n = n / 3;                       
                                                 }                       
                                                 // now we have to iterate only for integers                       
                                                 // who does not have prime factor 2 and 3                       
                                                 for                                     (                                     int                                     i = 5; i <= Math.Sqrt(n); i += 6) {                       
                                                 while                                     (n % i == 0) {                       
                                                 maxPrime = i;                       
                                                 n = n / i;                       
                                                 }                       
                                                 while                                     (n % (i + 2) == 0) {                       
                                                 maxPrime = i + 2;                       
                                                 n = n / (i + 2);                       
                                                 }                       
                                                 }                       
           
                                                 // This condition is to handle the case                       
                                                 // when n is a prime number greater than 4                       
                                                 if                                     (n > 4)                       
                                                 maxPrime = n;                       
           
                                                 return                                     maxPrime;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 long                                     n = 15L;                       
                                                 Console.WriteLine(maxPrimeFactors(n));                       
           
                                                 n = 25698751364526L;                       
                                                 Console.WriteLine(maxPrimeFactors(n));                       
                                                 }                       
                         }                       

PHP

                         <?php                       
                         // PHP Program to find                       
                         // largest prime factor                       
                         // of number                       
           
                         // A function to find                       
                         // largest prime factor                       
                         function                                     maxPrimeFactors(                                     $n                                     )                       
                         {                       
                                   
                                                 // Initialize the maximum                       
                                                 // prime factor variable                       
                                                 // with the lowest one                       
                                                 $maxPrime                                     = -1;                       
           
                                                 // Print the number of                       
                                                 // 2s that divide n                       
                                                 while                                     (                                     $n                                     % 2 == 0)                       
                                                 {                       
                                                 $maxPrime                                     = 2;                       
                                   
                                                 // equivalent to n /= 2                       
                                                 $n                                     >>= 1;                       
                                                 }                       
                                                 // n must be odd at this point                       
                                                 while                                     (                                     $n                                     % 3 == 0) {                       
                                                 $maxPrime                                     = 3;                       
                                                 $n                                     =                                     $n                                     /3;                       
                                                 }                       
                                                 // now we have to iterate only for integers                       
                                                 // who does not have prime factor 2 and 3                       
                                                 for                                     (                                     $i                                     = 3;                                     $i                                     <= sqrt(                                     $n                                     );                                     $i                                     += 2)                       
                                                 {                       
                                                 while                                     (                                     $n                                     %                                     $i                                     == 0)                       
                                                 {                       
                                                 $maxPrime                                     =                                     $i                                     ;                       
                                                 $n                                     =                                     $n                                     /                                     $i                                     ;                       
                                                 }                       
                                                 while                                     (                                     $n                                     % (                                     $i                                     +2) == 0) {                       
                                                 $maxPrime                                     =                                     $i                                     +2;                       
                                                 $n                                     =                                     $n                                     / (                                     $i                                     +2);                       
                                                 }                       
                                                 }                       
           
                                                 // This condition is                       
                                                 // to handle the case                       
                                                 // when n is a prime                       
                                                 // number greater than 4                       
                                                 if                                     (                                     $n                                     > 4)                       
                                                 $maxPrime                                     =                                     $n                                     ;                       
           
                                                 return                                     $maxPrime                                     ;                       
                         }                       
           
                                                 // Driver Code                       
                                                 $n                                     = 15;                       
                                                 echo                                     maxPrimeFactors(                                     $n                                     ),                                     ""                                     ;                       
           
                                                 $n                                     = 25698751364526;                       
                                                 echo                                     maxPrimeFactors(                                     $n                                     ),                                     ""                                     ;                       
           
           
                         ?>                       

Javascript

                         <script>                       
                         // Javascript program to find largest prime factor                       
                         function                                     maxPrimeFactor(n) {                       
                                                 let maxPrime = -1;                       
                                                 while                                     (n % 2 == 0) {                       
                                                 n = n / 2;                       
                                                 maxPrime = 2;                       
                                                 }                       
           
                                                 while                                     (n % 3 == 0) {                       
                                                 n = n / 3;                       
                                                 maxPrime = 3;                       
                                                 }                       
           
                                                 for                                     (let i = 5; i <= Math.sqrt(n); i += 6) {                       
                                                 while                                     (n % i == 0) {                       
                                                 maxPrime = i;                       
                                                 n = n / i;                       
                                                 }                       
                                                 while                                     (n % (i + 2) == 0) {                       
                                                 maxPrime = i + 2;                       
                                                 n = n / (i + 2);                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     n > 4 ? n : maxPrime;                       
                         }                       
           
                         document.write(maxPrimeFactor(15));                       
                         document.write(maxPrimeFactor(25698751364526));                       
           
                         // This code is contributed by 8chkh7v1i3lrbhuvxyg3d9gbg9e097eodfhj7qbz.                       
                         </script>                       

输出

时间复杂性： $ext{O}(sqrt{n})$ 辅助空间： $ext{O}(1)$

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章