首页 > 代码库 > USACO sprime
USACO sprime
/* ID:kevin_s1 PROG:sprime LANG:C++ */
//N = 1只可能为2,3,5,7,N > 1只可能为1,3,7,9. N = i,到N = i + 1递推如果是素数就扩展,类似于BFS
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <map> #include <set> #include <algorithm> #include <cstdlib> #include <list> #include <cmath> using namespace std; //gobal variable==== vector<vector<int> > prime(9); int N; //================== //function========== bool isPrime(int i) { bool tag = true; int place = (int)sqrt((double)i); int value; for(int j = 3; j <= place; j+=2)//质数判别 { if(i % j == 0) { tag = false; break; } } return tag; } //================== int main(){ freopen("sprime.in","r",stdin); freopen("sprime.out","w",stdout); cin>>N; prime[1].push_back(2); prime[1].push_back(3); prime[1].push_back(5); prime[1].push_back(7); for(int i = 2; i <= N; i++){ for(int j = 0; j < prime[i - 1].size(); j++){ long long num = prime[i - 1][j] * 10; if(isPrime(num + 1)) prime[i].push_back(num + 1); if(isPrime(num + 3)) prime[i].push_back(num + 3); if(isPrime(num + 7)) prime[i].push_back(num + 7); if(isPrime(num + 9)) prime[i].push_back(num + 9); } } for(int i = 0; i < prime[N].size(); i++){ cout<<prime[N][i]<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。