cpp-project-euler/P051.cpp at master · ebecz/cpp-project-euler · GitHub

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
#include <iostream>
#include <cstring>
using namespace std;
const unsigned int N=1000000;
const unsigned int Target=7;
bool P[N];
unsigned int P051(){
    memset(P,true,sizeof(P));
    P[0]=false;
    P[1]=false;
    for(unsigned int i=2;i<N;i++){
        if(P[i]){
            for(unsigned int j=2;j*i<N;j++){
                P[i*j]=0;
            }
        }
    }
    for(unsigned int i=0;i<N;i++){
        if(P[i]){
            unsigned int S=0,M=1;
            unsigned int D[30];
            for(unsigned int u=i;u;S++){
                D[S]=u%10;
                u/=10;
                M*=10;
            }
            M/=10;
            for(unsigned int q=1;q<(1<<S);q++){
                unsigned int N=0,U=0;
                for(unsigned int p=0,Dz=1;p<S;p++,Dz*=10){
                    if(q&(1<<p)){
                        U+=Dz;
                    }else{
                        N+=D[p]*Dz;
                    }
                }
                {
                    unsigned int s=0;
                    for(unsigned int k=0;(k-s<=10-Target) && k<10;k++){
                        if(P[N+U*k]){
                            if(N+U*k>=M){
                                s++;
                            }
                        }
                    }
                    if(s==Target){
                        for(unsigned int k=0;k<10;k++){
                            if(P[N+U*k]){
                                if(N+U*k>=M){
                                    return N+U*k;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return 0;
}
int main() {
    cout<<P051()<<endl;
    return 0;
}