简答题 偏难
#20051

数字选取

数字选取

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false;">#include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; using namespace std; const int N = 1e5 + 5; int n, p[N], cnt, minp[N]; bool np[N], used[N]; int main() {     scanf("%d", &amp;n);     // 欧拉筛,同时求最小质因子minp     for (int i = 2; i &lt;= n; i++) {         if (!np[i]) {             p[++cnt] = i;             minp[i] = i;         }         for (int j = 1; j &lt;= cnt &amp;&amp; 1LL * i * p[j] &lt;= n; j++) {             np[i * p[j]] = true;             minp[i * p[j]] = p[j];             if (i % p[j] == 0) break;         }     }     int k = n / 2;     int res = 0;     for (int i = k + 1; i &lt;= n; i++) {         int prime = minp[i];         if (!used[prime]) {             used[prime] = true;             res++;         }     }     res += 1; // 选数字1     printf("%d\n", res);     return 0; }</pre>
这道题暂未补解析。