大数的素因子-yiteyi-C++库

给定一个数字N，打印出所有素数及其幂。这里N<=10^18 例如：

null

Input : 250 Output : 2  1         5  3Explanation: The prime factors of 250 are 2and 5. 2 appears once in the prime factorization of and 5 is thrice in it. Input : 1000000000000000000Output : 2  18         5  18Explanation: The prime factors of 1000000000000000000are 2 and 5. The prime factor 2 appears 18 times in the prime factorization. 5 appears 18 times.

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

我们不能使用中国的实施对于单个大数，因为它需要比例空间。我们首先计算2是给定数字的因子的次数，然后从 3至Sqrt（n） 为了得到一个质数除以一个特定的数的次数，这个数每次减少n/i。我们将我们的数n（其质数分解将被计算）除以它相应的最小质数因子，直到n变成1。如果在n>2的末尾，这意味着它是一个素数，所以我们打印这个特定的数字。

C++

                         // CPP program to print prime factors and their                       
                         // powers.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to calculate all the prime factors and                       
                         // count of every prime factor                       
                         void                                     factorize(                                     long                                     long                                     n)                       
                         {                       
                                                 int                                     count = 0;                       
           
                                                 // count the number of times 2 divides                       
                                                 while                                     (!(n % 2)) {                       
                                                 n >>= 1;                                     // equivalent to n=n/2;                       
                                                 count++;                       
                                                 }                       
           
                                                 // if 2 divides it                       
                                                 if                                     (count)                       
                                                 cout << 2 <<                                     "  "                                     << count << endl;                       
           
                                                 // check for all the possible numbers that can                       
                                                 // divide it                       
                                                 for                                     (                                     long                                     long                                     i = 3; i <=                                     sqrt                                     (n); i += 2) {                       
                                                 count = 0;                       
                                                 while                                     (n % i == 0) {                       
                                                 count++;                       
                                                 n = n / i;                       
                                                 }                       
                                                 if                                     (count)                       
                                                 cout << i <<                                     "  "                                     << count << endl;                       
                                                 }                       
           
                                                 // if n at the end is a prime number.                       
                                                 if                                     (n > 2)                       
                                                 cout << n <<                                     "  "                                     << 1 << endl;                       
                         }                       
           
                         // driver program to test the above function                       
                         int                                     main()                       
                         {                       
                                                 long                                     long                                     n = 1000000000000000000;                       
                                                 factorize(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         //Java program to print prime                       
                         // factors and their powers.                       
           
                         class                                     GFG {                       
           
                         // function to calculate all the                       
                         // prime factors and count of                       
                         // every prime factor                       
                                                 static                                     void                                     factorize(                                     long                                     n) {                       
                                                 int                                     count =                                     0                                     ;                       
           
                                                 // count the number of times 2 divides                       
                                                 while                                     (!(n %                                     2                                     >                                     0                                     )) {                       
                                                 // equivalent to n=n/2;                       
                                                 n >>=                                     1                                     ;                       
           
                                                 count++;                       
                                                 }                       
           
                                                 // if 2 divides it                       
                                                 if                                     (count >                                     0                                     ) {                       
                                                 System.out.println(                                     "2"                                     +                                     " "                                     + count);                       
                                                 }                       
           
                                                 // check for all the possible                       
                                                 // numbers that can divide it                       
                                                 for                                     (                                     long                                     i =                                     3                                     ; i <= (                                     long                                     ) Math.sqrt(n); i +=                                     2                                     ) {                       
                                                 count =                                     0                                     ;                       
                                                 while                                     (n % i ==                                     0                                     ) {                       
                                                 count++;                       
                                                 n = n / i;                       
                                                 }                       
                                                 if                                     (count >                                     0                                     ) {                       
                                                 System.out.println(i +                                     " "                                     + count);                       
                                                 }                       
                                                 }                       
           
                                                 // if n at the end is a prime number.                       
                                                 if                                     (n >                                     2                                     ) {                       
                                                 System.out.println(n +                                     " "                                     +                                     "1"                                     );                       
                                                 }                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String[] args) {                       
                                                 long                                     n = 1000000000000000000L;                       
                                                 factorize(n);                       
                                                 }                       
                         }                       
           
                         /*This code is contributed by 29AjayKumar*/                       

Python3

                         # Python3 program to print prime factors                       
                         # and their powers.                       
                         import                                     math                       
           
                         # Function to calculate all the prime                       
                         # factors and count of every prime factor                       
                         def                                     factorize(n):                       
                                                 count                                     =                                     0                                     ;                       
           
                                                 # count the number of                       
                                                 # times 2 divides                       
                                                 while                                     ((n                                     %                                     2                                     >                                     0                                     )                                     =                                     =                                     False                                     ):                       
                                   
                                                 # equivalent to n = n / 2;                       
                                                 n >>                                     =                                     1                                     ;                       
                                                 count                                     +                                     =                                     1                                     ;                       
           
                                                 # if 2 divides it                       
                                                 if                                     (count >                                     0                                     ):                       
                                                 print                                     (                                     2                                     , count);                       
           
                                                 # check for all the possible                       
                                                 # numbers that can divide it                       
                                                 for                                     i                                     in                                     range                                     (                                     3                                     ,                                     int                                     (math.sqrt(n))                                     +                                     1                                     ):                       
                                                 count                                     =                                     0                                     ;                       
                                                 while                                     (n                                     %                                     i                                     =                                     =                                     0                                     ):                       
                                                 count                                     +                                     =                                     1                                     ;                       
                                                 n                                     =                                     int                                     (n                                     /                                     i);                       
                                                 if                                     (count >                                     0                                     ):                       
                                                 print                                     (i, count);                       
                                                 i                                     +                                     =                                     2                                     ;                       
           
                                                 # if n at the end is a prime number.                       
                                                 if                                     (n >                                     2                                     ):                       
                                                 print                                     (n,                                     1                                     );                       
           
                         # Driver Code                       
                         n                                     =                                     1000000000000000000                                     ;                       
                         factorize(n);                       
           
                         # This code is contributed by mits                       

C#

                         // C# program to print prime                       
                         // factors and their powers.                       
                         using                                     System;                       
           
                         public                                     class                                     GFG                       
                         {                       
           
                         // function to calculate all the                       
                         // prime factors and count of                       
                         // every prime factor                       
                         static                                     void                                     factorize(                                     long                                     n)                       
                         {                       
                                                 int                                     count = 0;                       
           
                                                 // count the number of times 2 divides                       
                                                 while                                     (! (n % 2 > 0))                       
                                                 {                       
                                                 // equivalent to n=n/2;                       
                                                 n >>= 1;                       
                                   
                                                 count++;                       
                                                 }                       
           
                                                 // if 2 divides it                       
                                                 if                                     (count > 0)                       
                                                 Console.WriteLine(                                     "2"                                     +                                     " "                                     +count);                       
           
                                                 // check for all the possible                       
                                                 // numbers that can divide it                       
                                                 for                                     (                                     long                                     i = 3; i <= (                                     long                                     )                       
                                                 Math.Sqrt(n); i += 2)                       
                                                 {                       
                                                 count = 0;                       
                                                 while                                     (n % i == 0) {                       
                                                 count++;                       
                                                 n = n / i;                       
                                                 }                       
                                                 if                                     (count > 0)                       
                                                 Console.WriteLine(i +                                     " "                                     + count);                       
                                                 }                       
           
                                                 // if n at the end is a prime number.                       
                                                 if                                     (n > 2)                       
                                                 Console.WriteLine(n +                                     " "                                     +                                     "1"                                     );                       
                         }                       
           
                                                 // Driver Code                       
                                                 static                                     public                                     void                                     Main ()                       
                                                 {                       
                                                 long                                     n = 1000000000000000000;                       
                                                 factorize(n);                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to print prime                       
                         // factors and their powers.                       
           
                         // function to calculate all                       
                         // the prime factors and count                       
                         // of every prime factor                       
                         function                                     factorize(                                     $n                                     )                       
                         {                       
                                                 $count                                     = 0;                       
           
                                                 // count the number of                       
                                                 // times 2 divides                       
                                                 while                                     (!(                                     $n                                     % 2))                       
                                                 {                       
                                                 // equivalent to n = n / 2;                       
                                                 $n                                     >>= 1;                       
                                                 $count                                     ++;                       
                                                 }                       
           
                                                 // if 2 divides it                       
                                                 if                                     (                                     $count                                     )                       
                                                 echo                                     (2 .                                     " "                                     .                                     $count                                     .                                     ""                                     );                       
           
                                                 // check for all the possible                       
                                                 // numbers that can divide it                       
                                                 for                                     (                                     $i                                     = 3;                                     $i                                     <= sqrt(                                     $n                                     );                                     $i                                     += 2)                       
                                                 {                       
                                                 $count                                     = 0;                       
                                                 while                                     (                                     $n                                     %                                     $i                                     == 0)                       
                                                 {                       
                                                 $count                                     ++;                       
                                                 $n                                     =                                     $n                                     /                                     $i                                     ;                       
                                                 }                       
                                                 if                                     (                                     $count                                     )                       
                                                 echo                                     (                                     $i                                     .                                     " "                                     .                                     $count                                     );                       
                                                 }                       
           
                                                 // if n at the end is a prime number.                       
                                                 if                                     (                                     $n                                     > 2)                       
                                                 echo                                     (                                     $n                                     .                                     " "                                     . 1);                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 1000000000000000000;                       
                         factorize(                                     $n                                     );                       
           
                         // This code is contributed by Ajit.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to print prime factors and their                       
                         // powers.                       
           
                         // function to calculate all the prime factors and                       
                         // count of every prime factor                       
                         function                                     factorize(n)                       
                         {                       
                                                 var                                     count = 0;                       
           
                                                 // count the number of times 2 divides                       
                                                 while                                     ((n % 2)==0) {                       
                                                 n = parseInt(n/2)                                     // equivalent to n=n/2;                       
                                                 count++;                       
                                                 }                       
                                   
                                                 // if 2 divides it                       
                                                 if                                     (count)                       
                                                 document.write( 2 +                                     "  "                                     + count +                                     "<br>"                                     );                       
           
                                                 // check for all the possible numbers that can                       
                                                 // divide it                       
                                                 for                                     (                                     var                                     i = 3; i <= parseInt(Math.sqrt(n)); i += 2) {                       
                                                 count = 0;                       
                                                 while                                     (n % i == 0) {                       
                                                 count++;                       
                                                 n = parseInt(n / i);                       
                                                 }                       
                                                 if                                     (count!=0)                       
                                                 document.write( i +                                     "  "                                     + count +                                     "<br>"                                     );                       
                                                 }                       
           
                                                 // if n at the end is a prime number.                       
                                                 if                                     (n > 2)                       
                                                 document.write( n +                                     "  "                                     + 1 +                                     "<br>"                                     );                       
                         }                       
           
                         // driver program to test the above function                       
                         var                                     n = 1000000000000000000;                       
                         factorize(n);                       
           
                         </script>                       

输出：

2 185 18

时间复杂性： O（sqrt（n））。

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

THE END

技术文章