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
| #include <bits/stdc++.h> # define pi pair<int,int> using namespace std; typedef long long ll; const int Q1=5678027,Q2=7208785; bool b[Q2*5+2]; ll pr[Q2 + 104]; int p=0;
vector<pi>dr[3][3]; int dx[8]={-1,-1,-1,0,0,1,1,1},dy[8]={-1,0,1,-1,1,-1,0,1}; ll st(ll n){ return n*(n-1)/2+1; }
bool is_prime(int n, int d, int y){ if(y<0||y>=n+d) return false; else{ n-=2;d+=2; return !b[y+(n+n+d-1)*d/2]; } }
bool is_answer(int n,int y){ if(!is_prime(n, 0, y)) return false; int cnt=0; for(int k=0;k<8;k++){ if(dx[k]==0) continue; if(is_prime(n, dx[k], y + dy[k])){ if(++cnt>=2) return true; for(auto &[ox,oy]:dr[dx[k]+1][dy[k]+1]){ if(is_prime(n, ox, y + oy)) return true; } } } return false; } ll solve(int row){ ll l=st(row-2),r=st(row+3)-1; ll sq=sqrt(r); p=0; memset(b,0,sizeof(b)); for(int i=2;i<=sq;i++){ if(b[i]) continue; pr[++p]=i; for(int j=i;1ll*i*j<=sq;j++) b[i*j]=true; } memset(b,0,sizeof(b)); for(int i=1; i <= p; i++) for(ll j= (l + pr[i] - 1) / pr[i]; j * pr[i] <= r; j++) b[j * pr[i] - l]=true; ll ans=0,nl=st(row); for(int y=0;y<row;y++) if(is_answer(row,y)) ans+=nl+y; return ans; } int main(){ for(int i=-1;i<=1;i++){ for(int j=-1;j<=1;j++){ if(i==0) continue; for(int k=0;k<8;k++){ int x=i+dx[k],y=j+dy[k]; if(max(abs(x),abs(y))==2){ dr[i+1][j+1].push_back(pi(x,y)); } } } } ll ans = solve(Q1) + solve(Q2); printf("%lld\n",ans); }
|