特殊筛选中未标记整数的数量-yiteyi-C++库

给予 数组A 包含来自 2比N。 .对其进行特殊类型的筛分。筛分程序如下：

null

创建一个数组，将元素作为从2到N的连续整数，并将数组中的每个元素标记为未标记。
设一个整数 Q=N 和 做记号 所有的真除数 Q 除了数组中的Q本身。
找到小于Q的最大未标记数，并将Q分配给它，然后从第2步开始重复。如果没有更多未标记的元素，则停止。

筛选后找出未标记整数的数量。 例如：

Input : N = 5 Output : Number of unmarked elements = 3Explanation : We create array A[] = { 2, 3, 4, 5 }.2 is marked as it is a proper divisor of 4.Input : N = 4Output : Number of unmarked elements = 2

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

天真的方法： 一种基本方法是运行两个循环。外循环遍历整个数组，内循环遍历2–Q，通过检查取消标记Q的所有适当因子 a[i]%Q=0。 时间复杂性： O（N^2） 有效方法： 一个简单的观察表明，实际上没有必要在这里进行筛选，而是N的值将决定答案。 案例1： 如果N是 古怪的 那么未标记元素的数量将为（N/2）+1。 案例2： 如果N是即使那么未标记元素的数量将为（N/2）。 时间复杂性： O（1） 例如：

输入：N=5 产出：3 A[]={2,3,4,5} 步骤： 1.）Q=5：标记Q的所有适当因子，这里没有元素，因此每个元素都保持未标记状态。 3.）Q=4：标记Q的所有适当因子。这里2被标记，而未标记的元素是{3,4,5}。 5.）Q=3： 6.）现在不能再做标记了，所以到此为止所以未标记元素的数量是3，即{3，4，5} 如果N的值为奇数，则结果应为（N/2）+1=（3/2）+1=（5/2）+1=2+1=3。输入：N=4 产出：2 A[]={2,3,4} 步骤： 1.）Q=4标记Q的所有适当因子。所以这里2被标记，而未标记的元素是{3，4} 3.）Q=3 4.）现在不能再做标记了，所以到此为止因此，筛分后未标记元素的数量为{3，4}=2 如果N为偶数，则结果应为（N/2）=（4/2）=2

C++

                         // C++ Program to determine the                       
                         // number of unmarked integers in                       
                         // a special sieve                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         int                                     countUnmarked(                                     int                                     N)                       
                         {                       
                                                 if                                     (N % 2 == 0)                       
                                                 return                                     N/2;                       
                                                 else                       
                                                 return                                     N/2 + 1;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     N = 4;                       
                                                 cout <<                                     "Number of unmarked elements: "                       
                                                 << countUnmarked(N) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Program to determine                       
                         // the number of unmarked                       
                         // integers in a special sieve                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                         static                                     int                                     countUnmarked(                                     int                                     N)                       
                         {                       
                                                 if                                     (N %                                     2                                     ==                                     0                                     )                       
                                                 return                                     N /                                     2                                     ;                       
                                                 else                       
                                                 return                                     N /                                     2                                     +                                     1                                     ;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     N =                                     4                                     ;                       
                                                 System.out.println(                                     "Number of unmarked "                                     +                       
                                                 "elements: "                                     +                       
                                                 countUnmarked(N));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by anuj_67.                       

Python3

                         # Python3 Program to determine                       
                         # the number of unmarked                       
                         # integers in a special sieve                       
                         def                                     countUnmarked(N):                       
                                                 if                                     (N                                     %                                     2                                     =                                     =                                     0                                     ):                       
                                                 return                                     N                                     /                                     2                                     ;                       
                                                 else                                     :                       
                                                 return                                     N                                     /                                     2                                     +                                     1                                     ;                       
           
                         # Driver Code                       
                         N                                     =                                     4                                     ;                       
                         print                                     (                                     "Number of unmarked elements:"                                     ,                       
                                                 int                                     (countUnmarked(N)));                       
                                   
                         # This code is contributed                       
                         # by mits                       

C#

                         // C# Program to determine                       
                         // the number of unmarked                       
                         // integers in a special sieve                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         static                                     int                                     countUnmarked(                                     int                                     N)                       
                         {                       
                                                 if                                     (N % 2 == 0)                       
                                                 return                                     N / 2;                       
                                                 else                       
                                                 return                                     N / 2 + 1;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main ()                       
                         {                       
                                                 int                                     N = 4;                       
                                                 Console.WriteLine(                                     "Number of unmarked "                                     +                       
                                                 "elements: "                                     +                       
                                                 countUnmarked(N));                       
                         }                       
                         }                       
           
                         // This code is contributed                       
                         // by anuj_67.                       

PHP

                         <?php                       
                         // PHP Program to determine                       
                         // the number of unmarked                       
                         // integers in a special sieve                       
           
                         function                                     countUnmarked(                                     $N                                     )                       
                         {                       
                                                 if                                     (                                     $N                                     % 2 == 0)                       
                                                 return                                     $N                                     / 2;                       
                                                 else                       
                                                 return                                     $N                                     / 2 + 1;                       
                         }                       
           
                         // Driver Code                       
                         $N                                     = 4;                       
                         echo                                     "Number of unmarked elements: "                                     ,                       
                                                 countUnmarked(                                     $N                                     );                       
                                   
                         // This code is contributed                       
                         // by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
                         // javascript Program to determine                       
                         // the number of unmarked                       
                         // integers in a special sieve                       
                                                 function                                     countUnmarked(N) {                       
                                                 if                                     (N % 2 == 0)                       
                                                 return                                     N / 2;                       
                                                 else                       
                                                 return                                     N / 2 + 1;                       
                                                 }                       
           
                                                 // Driver Code                       
                                   
                                                 var                                     N = 4;                       
                                                 document.write(                                     "Number of unmarked "                       
                                                 +                                     "elements: "                                     + countUnmarked(N));                       
           
                         // This code is contributed by todaysgaurav                       
                         </script>                       

输出：

Number of unmarked elements: 2

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

THE END

技术文章