特殊质数构造
題目：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1226
?
題目：https://projecteuler.net/problem=291
?
題意：如果質(zhì)數(shù)可以由如下公式構(gòu)造出來，那么稱質(zhì)數(shù)是可造的。
?
????
?
???? 給定一個(gè)區(qū)間，求在這個(gè)區(qū)間內(nèi)有多少個(gè)可造的質(zhì)數(shù)，其中。
?
?
分析：把原式進(jìn)行化簡(jiǎn)得到
?
????
?
???? 設(shè)，，且有和，那么繼續(xù)得到
?
????
?
???? 很明顯。那么得到
?
????
?
???? 繼續(xù)化簡(jiǎn)得到
?
????
?
???? 由于是素?cái)?shù)，那么，且，最終得到
?
????
??
???? 接下來，可以利用Brahmagupta–Fibonacci identity原理進(jìn)行篩選。
?
???? 最后附論文一篇：http://ami.ektf.hu/uploads/papers/finalpdf/AAPASM_25_from39to53.pdf
?
代碼：
#include <iostream> #include <string.h> #include <stdio.h> #include <vector>using namespace std; typedef long long LL;LL Solve(LL a, LL b) {vector<LL> v;for(LL i = 0; ;i++){LL t = 2 * i * i + 2 * i + 1;if(t > b) break;v.push_back(t);}int cnt = 0;for(LL i = 1; i < v.size(); i++){LL t = 2 * i * i + 2 * i + 1;LL x = v[i];if(t == x && t >= a)cnt++;if(x > 1){for(int j = i; j < v.size(); j += x)while(v[j] % x == 0)v[j] /= x;for(int j = x - i - 1; j < v.size(); j += x)while(v[j] % x == 0)v[j] /= x;}}return cnt; }int main() {LL a, b;while(cin >> a >> b)cout << Solve(a, b) << endl;return 0; }
?
?
總結(jié)
