題意
給你個數，讓你求出有多少種素數的組合使得兩個素數的和等於給你的這個數。數據範圍比較小，小於等於32768.
思路
沒啥好的數學辦法，但是數據範圍比較小，所以不妨嘗試打個素數表看看小於32768的素數有多少，打完了發現就3000多個，這樣的話即使是O(n^2)的時間複雜度也沒有問題。我們開個計數器數組，然後枚舉素數和，加到計數器上面，預處理好這些之後，直接受理查詢就可以了。
代碼
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
// // POJ2909.cpp // playground // // Created by Adam Chang on 2015/05/27. // Copyright (c) 2015年 Adam Chang. All rights reserved. // #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; #define MAXN 32800 bool prime[MAXN]; vector<int> primels; int cnt[MAXN]; bool isPrime(int n){ for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) { return false; } } return true; } void genPrime(){ memset(prime, true, sizeof(prime)); for (int i = 2; i < MAXN; i++) { if (prime[i]) { if (isPrime(i)) { for (int k = 2; k * i < MAXN; k++) { prime[k*i] = false; } }else{ prime[i] = false; continue; } }else{ continue; } } } int main(){ genPrime(); for (int i = 2; i <= MAXN; i++) { if (prime[i]) { primels.push_back(i); } } for (int i = 0; i < primels.size(); i++) { for (int j = i; j < primels.size(); j++) { if (primels[i] + primels[j] < MAXN) { cnt[primels[i] + primels[j]]++; } } } int q = 0; while (cin >> q && q) { cout << cnt[q] << endl; } return 0; } |
