给定一个数字N，打印1到N范围内的所有数字，其中正好有3个除数。
null
例如：
Input : N = 16Output : 4 94 and 9 have exactly three divisors.DivisorInput : N = 49Output : 4 9 25 494, 9, 25 and 49 have exactly three divisors.
仔细看了上面提到的例子之后，你注意到所有需要的数字都是完美的正方形，而且也只有素数。这背后的逻辑是，这样的数只能有三个数作为其除数，也包括1，而这个数本身只会导致一个除数，而不是一个数，所以我们可以很容易地得出结论，需要的是那些素数的平方，因此它们只能有三个除数（1，数本身和sqrt（数））。所有的素数i，使得i*i小于等于N，都是三个素数。
注： 我们可以使用任何筛选方法有效地生成一个集合中的所有素数，然后我们应该生成所有素数i，这样 i*i<=N .
以下是上述方法的实施情况：
C++
// C++ program to print all // three-primes smaller than // or equal to n using Sieve // of Eratosthenes #include <bits/stdc++.h> using namespace std; // Generates all primes upto n and // prints their squares void numbersWith3Divisors( int n) { bool prime[n+1]; memset (prime, true , sizeof (prime)); prime[0] = prime[1] = 0; for ( int p = 2; p*p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true ) { // Update all multiples of p for ( int i = p*2; i <= n; i += p) prime[i] = false ; } } // print squares of primes upto n. cout << "Numbers with 3 divisors :" ; for ( int i=0; i*i <= n ; i++) if (prime[i]) cout << i*i << " " ; } // Driver program int main() { // sieve(); int n = 96; numbersWith3Divisors(n); return 0; } |
JAVA
// Java program to print all // three-primes smaller than // or equal to n using Sieve // of Eratosthenes import java.io.*; import java.util.*; class GFG { // Generates all primes upto n // and prints their squares static void numbersWith3Divisors( int n) { boolean [] prime = new boolean [n+ 1 ]; Arrays.fill(prime, true ); prime[ 0 ] = prime[ 1 ] = false ; for ( int p = 2 ; p*p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true ) { // Update all multiples of p for ( int i=p* 2 ; i<=n; i += p) prime[i] = false ; } } // print squares of primes upto n System.out.println( "Numbers with 3 divisors : " ); for ( int i= 0 ; i*i <= n ; i++) if (prime[i]) System.out.print(i*i + " " ); } // Driver program public static void main (String[] args) { int n = 96 ; numbersWith3Divisors(n); } } // Contributed by Pramod Kumar |
Python3
# Python3 program to print # all three-primes smaller than # or equal to n using Sieve # of Eratosthenes # Generates all primes upto n # and prints their squares def numbersWith3Divisors(n): prime = [ True ] * (n + 1 ); prime[ 0 ] = prime[ 1 ] = False ; p = 2 ; while (p * p < = n): # If prime[p] is not changed, # then it is a prime if (prime[p] = = True ): # Update all multiples of p for i in range (p * 2 ,n + 1 ,p): prime[i] = False ; p + = 1 ; # print squares of primes upto n. print ( "Numbers with 3 divisors :" ); i = 0 ; while (i * i < = n): if (prime[i]): print (i * i,end = " " ); i + = 1 ; # Driver program n = 96 ; numbersWith3Divisors(n); # This code is contributed by mits |
C#
// C# program to print all // three-primes smaller than // or equal to n using Sieve // of Eratosthenes class GFG { // Generates all primes upto n // and prints their squares static void numbersWith3Divisors( int n) { bool [] prime = new bool [n+1]; prime[0] = prime[1] = true ; for ( int p = 2; p*p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == false ) { // Update all multiples of p for ( int i = p*2; i <= n; i += p) prime[i] = true ; } } // print squares of primes upto n System.Console.WriteLine( "Numbers with 3 divisors : " ); for ( int i=0; i*i <= n ; i++) if (!prime[i]) System.Console.Write(i*i + " " ); } // Driver program public static void Main() { int n = 96; numbersWith3Divisors(n); } } // This code is Contributed by mits |
PHP
<?php // PHP program to print all three-primes // smaller than or equal to n using Sieve // of Eratosthenes // Generates all primes upto n and // prints their squares function numbersWith3Divisors( $n ) { $prime = array_fill (0, $n + 1, true); $prime [0] = $prime [1] = false; for ( $p = 2; $p * $p <= $n ; $p ++) { // If prime[p] is not changed, // then it is a prime if ( $prime [ $p ] == true) { // Update all multiples of p for ( $i = $p * 2; $i <= $n ; $i += $p ) $prime [ $i ] = false; } } // print squares of primes upto n. echo "Numbers with 3 divisors :" ; for ( $i = 0; $i * $i <= $n ; $i ++) if ( $prime [ $i ]) echo $i * $i . " " ; } // Driver Code $n = 96; numbersWith3Divisors( $n ); // This code is contributed by mits ?> |
Javascript
<script> // Javascript program to print all // three-primes smaller than // or equal to n using Sieve // of Eratosthenes // Generates all primes upto n and // prints their squares function numbersWith3Divisors(n) { let prime = new Array(n+1); prime.fill( true ); prime[0] = prime[1] = 0; for (let p = 2; p*p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true ) { // Update all multiples of p for (let i = p*2; i <= n; i += p) prime[i] = false ; } } // print squares of primes upto n. document.write( "Numbers with 3 divisors :" + "</br>" ); for (let i = 0; i*i <= n ; i++) if (prime[i]) document.write(i*i + " " ); } // sieve(); let n = 96; numbersWith3Divisors(n); // This code is contributed by mukesh07. </script> |
输出：
Numbers with 3 divisors :4 9 25 49
另一种方法：
要打印从1到N范围内的所有数字，其中正好有3个除数，主要的计算方法是找到那些素数的平方，并且小于或等于该数字。我们可以这样做：
- 开始整数的循环 我 从…起 2. 到 N
- 检查一下 我 是素数还是非素数，使用 iPrime（n） 方法
- 如果 我 是素数，检查其平方是否小于或等于给定的数。这将只检查素数的平方，因此减少了检查次数。
- 如果满足上述条件，将打印号码，循环将持续到 i<=n。
这样，就不需要额外的空间来存储任何东西。
这里是上述逻辑的一个实现，不需要使用额外的空间；
C++
// C++ program to print all // three-primes smaller than // or equal to n without using // extra space #include <bits/stdc++.h> using namespace std; void numbersWith3Divisors( int ); bool isPrime( int ); // Generates all primes upto n and // prints their squares void numbersWith3Divisors( int n) { cout << "Numbers with 3 divisors : " << endl; for ( int i = 2; i * i <= n; i++) { // Check prime if (isPrime(i)) { if (i * i <= n) { // Print numbers in // the order of // occurrence cout << i * i << " " ; } } } } // Check if a number is prime or not bool isPrime( int n) { for ( int i = 2; i * i <= n; i++) { if (n % i == 0) return false ; } return true ; } // Driver code int main() { int n = 122; numbersWith3Divisors(n); return 0; } // This code is contributed by vishu2908 |
JAVA
// Java program to print all // three-primes smaller than // or equal to n without using // extra space import java.util.*; class GFG { // 3 divisor logic implementation // check if a number is // prime or not // if it is a prime then // check if its square // is less than or equal to // the given number static void numbersWith3Divisors( int n) { System.out.println( "Numbers with 3 divisors : " ); for ( int i = 2 ; i * i <= n; i++) { // Check prime if (isPrime(i)) { if (i * i <= n) { // Print numbers in // the order of // occurrence System.out.print(i * i + " " ); } } } } // Check if a number is prime or not public static boolean isPrime( int n) { for ( int i = 2 ; i * i <= n; i++) { if (n % i == 0 ) return false ; } return true ; } // Driver program public static void main(String[] args) { int n = 122 ; numbersWith3Divisors(n); } } // Contributed by Parag Pallav Singh |
Python3
# Python3 program to print all # three-primes smaller than # or equal to n without using # extra space # 3 divisor logic implementation # check if a number is prime or # not if it is a prime then check # if its square is less than or # equal to the given number def numbersWith3Divisors(n): print ( "Numbers with 3 divisors : " ) i = 2 while i * i < = n: # Check prime if (isPrime(i)): if (i * i < = n): # Print numbers in the order # of occurrence print (i * i, end = " " ) i + = 1 # Check if a number is prime or not def isPrime(n): i = 2 while i * i < = n: if n % i = = 0 : return False i + = 1 return True # Driver code n = 122 numbersWith3Divisors(n) # This code is contributed by divyesh072019 |
C#
// C# program to print all // three-primes smaller than // or equal to n without using // extra space using System; class GFG{ // 3 divisor logic implementation // check if a number is prime or // not if it is a prime then check // if its square is less than or // equal to the given number static void numbersWith3Divisors( int n) { Console.WriteLine( "Numbers with 3 divisors : " ); for ( int i = 2; i * i <= n; i++) { // Check prime if (isPrime(i)) { if (i * i <= n) { // Print numbers in the order // of occurrence Console.Write(i * i + " " ); } } } } // Check if a number is prime or not public static bool isPrime( int n) { for ( int i = 2; i * i <= n; i++) { if (n % i == 0) return false ; } return true ; } // Driver code static void Main() { int n = 122; numbersWith3Divisors(n); } } // This code is contributed by divyeshrabadiya07 |
Javascript
<script> // Javascript program to print all // three-primes smaller than // or equal to n without using // extra space // 3 divisor logic implementation // check if a number is prime or // not if it is a prime then check // if its square is less than or // equal to the given number function numbersWith3Divisors(n) { document.write( "Numbers with 3 divisors : " ); for (let i = 2; i * i <= n; i++) { // Check prime if (isPrime(i)) { if (i * i <= n) { // Print numbers in the order // of occurrence document.write(i * i + " " ); } } } } // Check if a number is prime or not function isPrime(n) { if (n == 0 || n == 1) return false ; for (let i = 2; i * i <= n; i++) { if (n % i == 0) return false ; } return true ; } let n = 122; numbersWith3Divisors(n); // This code is contributed by suresh07. </script> |
输出：
Numbers with 3 divisors :4 9 25 49 121
本文由 希瓦姆·普拉丹（anuj_charm） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
