Project Euler Problem 51

发表于 | 分类于

Project Euler Problem 51 Prime digit replacements

题意

​ 将两位数*3的第一个数字代换为任意数字，在九个可能值中有六个是素数：13、23、43、53、73和83。

​ 将五位数56**3的第三和第四位数字代换为相同的任意数字，就得到了十个可能值中有七个是素数的最小例子，这个素数族是：56003、56113、56333、56443、56663、56773和56993。56003作为这一族中最小的成员，也是最小的满足这个性质的素数。

​ 通过将部分数字（不一定相邻）代换为相同的任意数字，有时能够得到八个素数，求满足这一性质的最小素数。

答案是*2*3*3

思路

​ (1)先打个素数表

​ (2)对每个素数进行位数计算(计算有几位)，然后枚举换哪一位（我用二进制下进行枚举，个位不能进行枚举，枚举个位的话有一般都是偶数，所有从十位开始枚举）

​ (3)用set存数最后计算set的大小是否等于8，输出结果。

代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int v[maxn];

void prime(int n){
	memset(v,0,sizeof v);
	for(int i=2;i<=n;i++){
		if(v[i]) continue;
		for(int j=i;j<=n/i;j++) v[i*j]=1;
	}
}

bool check(int n){
	int a[10];
	int x=n;
	int id=0;
	while(x>0){
		a[++id]=x%10;
		x/=10;
	}
	for(int i=1;i<(1<<(id-1));i++){
		set<int> s;
		for(int j=0;j<=9;j++){
			int b[10];
			for(int k=1;k<=id;k++) b[k]=a[k];
			for(int k=0;k<=4;k++)
				if(i&(1<<k)) b[k+2]=j;
			int ans=0;
			for(int k=id;k>=1;k--)  ans=ans*10+b[k];
			if(!v[ans]) 
				s.insert(ans);
		}
		if(*s.begin()==n&&s.size()==8) return 1;
	}
	return 0;
}
int main(){
	prime(maxn);
	for(int i=101;i<1000000;i+=2){
		if(!v[i]&&check(i)){
			printf("%d\n",i);
			break;
		}
	}
	//system("pause");
	return 0;
}