给定一个自然数n，打印它的所有不同除数。
null
例如：
Input : n = 10 Output: 1 2 5 10 Input: n = 100 Output: 1 2 4 5 10 20 25 50 100 Input: n = 125 Output: 1 5 25 125
请注意，此问题不同于 寻找所有主要因素 .
A. 天真的解决方案 将迭代从1到n的所有数字，检查该数字是否除以n并打印它。下面是一个同样的程序：
C++
// C++ implementation of Naive method to print all // divisors #include <iostream> using namespace std; // function to print the divisors void printDivisors( int n) { for ( int i = 1; i <= n; i++) if (n % i == 0) cout << " " << i; } /* Driver program to test above function */ int main() { cout << "The divisors of 100 are: " ; printDivisors(100); return 0; } // this code is contributed by shivanisinghss2110 |
C
// C implementation of Naive method to print all // divisors #include<stdio.h> // function to print the divisors void printDivisors( int n) { for ( int i=1;i<=n;i++) if (n%i==0) printf ( "%d " ,i); } /* Driver program to test above function */ int main() { printf ( "The divisors of 100 are: " ); printDivisors(100); return 0; } |
JAVA
// Java implementation of Naive method to print all // divisors class Test { // method to print the divisors static void printDivisors( int n) { for ( int i= 1 ;i<=n;i++) if (n%i== 0 ) System.out.print(i+ " " ); } // Driver method public static void main(String args[]) { System.out.println( "The divisors of 100 are: " ); printDivisors( 100 );; } } |
Python3
# Python implementation of Naive method # to print all divisors # method to print the divisors def printDivisors(n) : i = 1 while i < = n : if (n % i = = 0 ) : print (i,end = " " ) i = i + 1 # Driver method print ( "The divisors of 100 are: " ) printDivisors( 100 ) #This code is contributed by Nikita Tiwari. |
C#
// C# implementation of Naive method // to print all divisors using System; class GFG { // method to print the divisors static void printDivisors( int n) { for ( int i = 1; i <= n; i++) if (n % i == 0) Console.Write( i + " " ); } // Driver method public static void Main() { Console.Write( "The divisors of" , " 100 are: " ); printDivisors(100);; } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP implementation of Naive // method to print all divisors // function to print the divisors function printDivisors( $n ) { for ( $i = 1; $i <= $n ; $i ++) if ( $n % $i == 0) echo $i , " " ; } // Driver Code echo "The divisors of 100 are:" ; printDivisors(100); // This code is contributed by ajit ?> |
Javascript
<script> // Javascript implementation of Naive method to print all // divisors // function to print the divisors function printDivisors(n) { for (i=1;i<=n;i++) if (n%i==0) document.write(i+ " " ); } /* Driver program to test above function */ document.write( "The divisors of 100 are:" + "<br>" ); printDivisors(100); // This code is contributed by Mayank Tyagi </script> |
输出：
The divisors of 100 are: 1 2 4 5 10 20 25 50 100
时间复杂性： O（n） 辅助空间： O（1）
我们能改进上述解决方案吗？ 如果我们仔细观察，所有的除数都成对出现。例如，如果n=100，那么各种除数对是：（1100），（2,50），（4,25），（5,20），（10,10） 利用这一事实，我们可以大大加快我们的程序。 然而，我们必须小心，如果有两个相等的除数，比如（10，10）。在这种情况下，我们只打印其中一个。
以下是相同的实现：
C++
// A Better (than Naive) Solution to find all divisors #include <iostream> #include <math.h> using namespace std; // Function to print the divisors void printDivisors( int n) { // Note that this loop runs till square root for ( int i=1; i<= sqrt (n); i++) { if (n%i == 0) { // If divisors are equal, print only one if (n/i == i) cout << " " << i; else // Otherwise print both cout << " " << i << " " << n/i; } } } /* Driver program to test above function */ int main() { cout << "The divisors of 100 are: " ; printDivisors(100); return 0; } // this code is contributed by shivanisinghss2110 |
C
// A Better (than Naive) Solution to find all divisors #include <stdio.h> #include <math.h> // Function to print the divisors void printDivisors( int n) { // Note that this loop runs till square root for ( int i=1; i<= sqrt (n); i++) { if (n%i == 0) { // If divisors are equal, print only one if (n/i == i) printf ( "%d " , i); else // Otherwise print both printf ( "%d %d " , i, n/i); } } } /* Driver program to test above function */ int main() { printf ( "The divisors of 100 are: " ); printDivisors(100); return 0; } |
JAVA
// A Better (than Naive) Solution to find all divisors class Test { // method to print the divisors static void printDivisors( int n) { // Note that this loop runs till square root for ( int i= 1 ; i<=Math.sqrt(n); i++) { if (n%i== 0 ) { // If divisors are equal, print only one if (n/i == i) System.out.print( " " + i); else // Otherwise print both System.out.print(i+ " " + n/i + " " ); } } } // Driver method public static void main(String args[]) { System.out.println( "The divisors of 100 are: " ); printDivisors( 100 );; } } |
Python3
# A Better (than Naive) Solution to find all divisors import math # method to print the divisors def printDivisors(n) : # Note that this loop runs till square root i = 1 while i < = math.sqrt(n): if (n % i = = 0 ) : # If divisors are equal, print only one if (n / i = = i) : print (i,end = " " ) else : # Otherwise print both print (i , int (n / i), end = " " ) i = i + 1 # Driver method print ( "The divisors of 100 are: " ) printDivisors( 100 ) #This code is contributed by Nikita Tiwari. |
C#
// A Better (than Naive) Solution to // find all divisors using System; class GFG { // method to print the divisors static void printDivisors( int n) { // Note that this loop runs // till square root for ( int i = 1; i <= Math.Sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // print only one if (n / i == i) Console.Write(i + " " ); // Otherwise print both else Console.Write(i + " " + n / i + " " ); } } } // Driver method public static void Main() { Console.Write( "The divisors of " + "100 are: " ); printDivisors(100); } } // This code is contributed by Smitha |
PHP
<?php // A Better (than Naive) Solution // to find all divisors // Function to print the divisors function printDivisors( $n ) { // Note that this loop // runs till square root for ( $i = 1; $i <= sqrt( $n ); $i ++) { if ( $n % $i == 0) { // If divisors are equal, // print only one if ( $n / $i == $i ) echo $i , " " ; // Otherwise print both else echo $i , " " , $n / $i , " " ; } } } // Driver Code echo "The divisors of 100 are: " ; printDivisors(100); // This code is contributed by anuj_67. ?> |
Javascript
<script> // A Better (than Naive) Solution to find all divisors // Function to print the divisors function printDivisors(n) { // Note that this loop runs till square root for (let i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, print only one if (parseInt(n / i, 10) == i) document.write(i); // Otherwise print both else document.write(i + " " + parseInt(n / i, 10) + " " ); } } } // Driver code document.write( "The divisors of 100 are: </br>" ); printDivisors(100); // This code is contributed by divyesh072019 </script> |
输出：
The divisors of 100 are: 1 100 2 50 4 25 5 20 10
时间复杂度：O（sqrt（n）） 辅助空间：O（1）
但是解决方案中还有一个小问题，你能猜到吗？ 对输出不是我们使用蛮力技术得到的排序方式。请参考下面的O（sqrt（n））时间解决方案，它按排序顺序打印除数。 求自然数|集2的所有除数 本文由 阿什图什·库马尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
