一开始超时,想到是因为每输入一个n都要从头计算一遍,很多重复工作。
所以改用数组,计算出结果,然后查表即可
#include <iostream> #include <cmath> #define N 1000001 bool is_prime(int n); using namespace std; int main() { int T, n; int a[N]; a[0] = 0; for(int i = 1; i < N; i++) { a[i] = a[i - 1]; if(is_prime(i)) { a[i]++; } } cin >> T; while(T > 0) { cin >> n; cout << a[n] << endl; T--; } return 0; } bool is_prime(int n) { bool res = true; if(n < 2) { return false; } for(int i = 2; i <= sqrt(n); i++) { if(n % i == 0) { res = false; break; } } return res; }
但看到别人运行速度很快,自己仍然很慢。
看了别人的算法,主要思路是两数相乘的结果肯定不是质数。改进如下
#include <iostream> #define N 1000001 #define NSQRT 1000 using namespace std; int main() { int T, n; int a[N]={0}; /*注意初始化,不然结果每次运行都会不同*/ for(int i = 2; i <= NSQRT; i++) { if(a[i] == 0) { for(int j = i*i; j <= N; j += i) { a[j] = 1; } } } for(int i = 2; i < N; i++) { if(a[i] == 0) { a[i] = a[i - 1] + 1; } else { a[i] = a[i - 1]; } } cin >> T; while(T > 0) { cin >> n; cout << a[n] << endl; T--; } return 0; }
节省了每次判断是不是质数时,从2到sqrt(n)的循环