题目链接:
A-数数_牛客练习赛129 (nowcoder.com)
题目描述:
样例输入:
5
样例输出:
0
思路分析:
直接求偶数是困难的,之前好像听过:任何一个大于1的自然数N,都可以唯一分解成有限个质数的乘积。那么就是间接的去做,拿题目给的n - 1 - '奇数'
‘奇数’怎么去求:先快速求出n 里面的质数,考虑到时间复杂度,要用O(n)的快速筛取质数,质数本身是题目里面所描述的‘奇数’,可以在筛质数的时候进行 '奇数' +1, 然后在去枚举质数的幂。
for(int i = 1; primes[i] <= sqrt(n); i ++ ) ,但是我之前写的是 <= n 发现一直tle, 即使是加了 #define IOS 和 #define endl 仍然不行。然后去本地跑5000000(极端输入),发现到后面全部的质数都是进不到幂为2的,因此才想起来 <= sqrt(n)。
代码:
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;const int N = 5e6 + 10;int primes[N];
int f[N];
int cnt;
int ret = 0;
int n;
int t;void prime(int x) {for(int i = 2; i <= x; i ++ ) {if(!f[i]) { // 还没被标记呢 primes[ ++ cnt ] = i;// 记下来 if(i <= n)t ++ ;}for(int j = 1; primes[j] <= x / i; j ++ ) {f[i * primes[j]] = 1;if(i % primes[j] == 0) {break;}}}
}int ksm(int x, int y) {int t = 1;while(y) {if(y & 1) {t = t * x;} y >>= 1;x = x * x;}return t;
}signed main() {IOS;cin >> n;prime(5000000); for(int i = 1; primes[i] <= sqrt(n); i ++ ) {for(int j = 2; ; j ++ ) {if(pow(primes[i], j) <= n) {t ++ ; } else {break;}}}cout << n - t - 1 << endl;return 0;
}