第N个智能号码-yiteyi-C++库

给定一个数字n，找到第n个智能数字（1<=n<=1000）。智能数是一个至少有三个不同素数因子的数。我们得到的结果值上限为MAX

null

例如，30是第一个智能数，因为它有2，3，5作为不同的素数因子。42是第二个智能数，因为它有2，3，7作为不同的素数因子。 例如：

Input : n = 1
Output: 30
// three distinct prime factors 2, 3, 5

Input : n = 50
Output: 273
// three distinct prime factors 3, 7, 13

Input : n = 1000
Output: 2664
// three distinct prime factors 2, 3, 37

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

这个想法是基于埃拉托斯坦筛 .我们使用数组来使用数组素数[]来跟踪素数。我们还使用相同的数组来跟踪到目前为止看到的素因子的计数。每当计数达到3，我们就把数字加到结果中。

取数组primes[]并用0初始化它。
现在我们知道第一个素数是i=2，所以标记素数[2]=1，即；素数[i]=1表示“i”是素数。
现在遍历primes[]数组，用条件primes[j]-=1标记“i”的所有倍数，其中“j”是“i”的倍数，并检查条件primes[j]+3=0，因为每当primes[j]变为-3时，它表明之前它是三个不同的素数因子的倍数。如果条件 素数[j]+3=0 这意味着“j”是一个智能数字，所以将其存储在数组结果[]中。
现在对数组结果[]进行排序，并返回结果[n-1]。

下面是上述想法的实现。

C++

                         // C++ implementation to find n'th smart number                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                                   
                         // Limit on result                       
                         const                                     int                                     MAX = 3000;                       
                                   
                         // Function to calculate n'th smart number                       
                         int                                     smartNumber(                                     int                                     n)                       
                         {                       
                                                 // Initialize all numbers as not prime                       
                                                 int                                     primes[MAX] = {0};                       
                                   
                                                 // iterate to mark all primes and smart number                       
                                                 vector<                                     int                                     > result;                       
                                   
                                                 // Traverse all numbers till maximum limit                       
                                                 for                                     (                                     int                                     i=2; i<MAX; i++)                       
                                                 {                       
                                                 // 'i' is maked as prime number because                       
                                                 // it is not multiple of any other prime                       
                                                 if                                     (primes[i] == 0)                       
                                                 {                       
                                                 primes[i] = 1;                       
                                   
                                                 // mark all multiples of 'i' as non prime                       
                                                 for                                     (                                     int                                     j=i*2; j<MAX; j=j+i)                       
                                                 {                       
                                                 primes[j] -= 1;                       
                                   
                                                 // If i is the third prime factor of j                       
                                                 // then add it to result as it has at                       
                                                 // least three prime factors.                       
                                                 if                                     ( (primes[j] + 3) == 0)                       
                                                 result.push_back(j);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // Sort all smart numbers                       
                                                 sort(result.begin(), result.end());                       
                                   
                                                 // return n'th smart number                       
                                                 return                                     result[n-1];                       
                         }                       
                                   
                         // Driver program to run the case                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 50;                       
                                                 cout << smartNumber(n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java implementation to find n'th smart number                       
                         import                                     java.util.*;                       
                         import                                     java.lang.*;                       
                                   
                         class                                     GFG {                       
                                   
                                                 // Limit on result                       
                                                 static                                     int                                     MAX =                                     3000                                     ;                       
                                   
                                                 // Function to calculate n'th smart number                       
                                                 public                                     static                                     int                                     smartNumber(                                     int                                     n)                       
                                                 {                       
                                   
                                                 // Initialize all numbers as not prime                       
                                                 Integer[] primes =                                     new                                     Integer[MAX];                       
                                                 Arrays.fill(primes,                                     new                                     Integer(                                     0                                     ));                       
                                   
                                                 // iterate to mark all primes and smart                       
                                                 // number                       
                                                 Vector<Integer> result =                                     new                                     Vector<>();                       
                                   
                                                 // Traverse all numbers till maximum                       
                                                 // limit                       
                                                 for                                     (                                     int                                     i =                                     2                                     ; i < MAX; i++)                       
                                                 {                       
                                   
                                                 // 'i' is maked as prime number                       
                                                 // because it is not multiple of                       
                                                 // any other prime                       
                                                 if                                     (primes[i] ==                                     0                                     )                       
                                                 {                       
                                                 primes[i] =                                     1                                     ;                       
                                   
                                                 // mark all multiples of 'i'                       
                                                 // as non prime                       
                                                 for                                     (                                     int                                     j = i*                                     2                                     ; j < MAX; j = j+i)                       
                                                 {                       
                                                 primes[j] -=                                     1                                     ;                       
                                   
                                                 // If i is the third prime                       
                                                 // factor of j then add it                       
                                                 // to result as it has at                       
                                                 // least three prime factors.                       
                                                 if                                     ( (primes[j] +                                     3                                     ) ==                                     0                                     )                       
                                                 result.add(j);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // Sort all smart numbers                       
                                                 Collections.sort(result);                       
                                   
                                                 // return n'th smart number                       
                                                 return                                     result.get(n-                                     1                                     );                       
                                   
                                                 }                       
                                   
                                                 // Driver program to run the case                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     50                                     ;                       
                                                 System.out.println(smartNumber(n));                       
                                   
                                                 }                       
                         }                       
                                   
                         // This code is contributed by Prasad Kshirsagar                       

Python3

                         # Python3 implementation to find                       
                         # n'th smart number                       
                                   
                         # Limit on result                       
                         MAX                                     =                                     3000                                     ;                       
                                   
                         # Function to calculate n'th                       
                         # smart number                       
                         def                                     smartNumber(n):                       
                                   
                                                 # Initialize all numbers as not prime                       
                                                 primes                                     =                                     [                                     0                                     ]                                     *                                     MAX                                     ;                       
                                   
                                                 # iterate to mark all primes                       
                                                 # and smart number                       
                                                 result                                     =                                     [];                       
                                   
                                                 # Traverse all numbers till maximum limit                       
                                                 for                                     i                                     in                                     range                                     (                                     2                                     ,                                     MAX                                     ):                       
                                   
                                                 # 'i' is maked as prime number because                       
                                                 # it is not multiple of any other prime                       
                                                 if                                     (primes[i]                                     =                                     =                                     0                                     ):                       
                                                 primes[i]                                     =                                     1                                     ;                       
                                   
                                                 # mark all multiples of 'i' as non prime                       
                                                 j                                     =                                     i                                     *                                     2                                     ;                       
                                                 while                                     (j <                                     MAX                                     ):                       
                                                 primes[j]                                     -                                     =                                     1                                     ;                       
                                   
                                                 # If i is the third prime factor of j                       
                                                 # then add it to result as it has at                       
                                                 # least three prime factors.                       
                                                 if                                     ( (primes[j]                                     +                                     3                                     )                                     =                                     =                                     0                                     ):                       
                                                 result.append(j);                       
                                                 j                                     =                                     j                                     +                                     i;                       
                                   
                                                 # Sort all smart numbers                       
                                                 result.sort();                       
                                   
                                                 # return n'th smart number                       
                                                 return                                     result[n                                     -                                     1                                     ];                       
                                   
                         # Driver Code                       
                         n                                     =                                     50                                     ;                       
                         print                                     (smartNumber(n));                       
                                   
                         # This code is contributed by mits                       

C#

                         // C# implementation to find n'th smart number                       
                         using                                     System.Collections.Generic;                       
                                   
                         class                                     GFG {                       
                                   
                                                 // Limit on result                       
                                                 static                                     int                                     MAX = 3000;                       
                                   
                                                 // Function to calculate n'th smart number                       
                                                 public                                     static                                     int                                     smartNumber(                                     int                                     n)                       
                                                 {                       
                                   
                                                 // Initialize all numbers as not prime                       
                                                 int                                     [] primes =                                     new                                     int                                     [MAX];                       
                                   
                                                 // iterate to mark all primes and smart                       
                                                 // number                       
                                                 List<                                     int                                     > result =                                     new                                     List<                                     int                                     >();                       
                                   
                                                 // Traverse all numbers till maximum                       
                                                 // limit                       
                                                 for                                     (                                     int                                     i = 2; i < MAX; i++)                       
                                                 {                       
                                   
                                                 // 'i' is maked as prime number                       
                                                 // because it is not multiple of                       
                                                 // any other prime                       
                                                 if                                     (primes[i] == 0)                       
                                                 {                       
                                                 primes[i] = 1;                       
                                   
                                                 // mark all multiples of 'i'                       
                                                 // as non prime                       
                                                 for                                     (                                     int                                     j = i*2; j < MAX; j = j+i)                       
                                                 {                       
                                                 primes[j] -= 1;                       
                                   
                                                 // If i is the third prime                       
                                                 // factor of j then add it                       
                                                 // to result as it has at                       
                                                 // least three prime factors.                       
                                                 if                                     ( (primes[j] + 3) == 0)                       
                                                 result.Add(j);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // Sort all smart numbers                       
                                                 result.Sort();                       
                                   
                                                 // return n'th smart number                       
                                                 return                                     result[n-1];                       
                                   
                                                 }                       
                                   
                                                 // Driver program to run the case                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 50;                       
                                                 System.Console.WriteLine(smartNumber(n));                       
                                   
                                                 }                       
                         }                       
                                   
                         // This code is contributed by mits                       

PHP

                         <?php                       
                         // PHP implementation to find n'th smart number                       
                                   
                         // Limit on result                       
                         $MAX                                     = 3000;                       
                                   
                         // Function to calculate n'th smart number                       
                         function                                     smartNumber(                                     $n                                     )                       
                         {                       
                                                 global                                     $MAX                                     ;                       
                                                 // Initialize all numbers as not prime                       
                                                 $primes                                     =                                     array_fill                                     (0,                                     $MAX                                     ,0);                       
                                   
                                                 // iterate to mark all primes and smart number                       
                                                 $result                                     =                                     array                                     ();                       
                                   
                                                 // Traverse all numbers till maximum limit                       
                                                 for                                     (                                     $i                                     =2;                                     $i                                     <                                     $MAX                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // 'i' is maked as prime number because                       
                                                 // it is not multiple of any other prime                       
                                                 if                                     (                                     $primes                                     [                                     $i                                     ] == 0)                       
                                                 {                       
                                                 $primes                                     [                                     $i                                     ] = 1;                       
                                   
                                                 // mark all multiples of 'i' as non prime                       
                                                 for                                     (                                     $j                                     =                                     $i                                     *2;                                     $j                                     <                                     $MAX                                     ;                                     $j                                     =                                     $j                                     +                                     $i                                     )                       
                                                 {                       
                                                 $primes                                     [                                     $j                                     ] -= 1;                       
                                   
                                                 // If i is the third prime factor of j                       
                                                 // then add it to result as it has at                       
                                                 // least three prime factors.                       
                                                 if                                     ( (                                     $primes                                     [                                     $j                                     ] + 3) == 0)                       
                                                 array_push                                     (                                     $result                                     ,                                     $j                                     );                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // Sort all smart numbers                       
                                                 sort(                                     $result                                     );                       
                                   
                                                 // return n'th smart number                       
                                                 return                                     $result                                     [                                     $n                                     -1];                       
                         }                       
                                   
                         // Driver program to run the case                       
                                   
                                                 $n                                     = 50;                       
                                                 echo                                     smartNumber(                                     $n                                     );                       
                                   
                         // This code is contributed by mits                       
                         ?>                       

输出：

本文由 沙克·米什拉（古卢） .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用贡献极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章