Problem 47 HARD
作法:預測(數學)
想法:利用陣列
(此題與Problem 47 做法不同 用暴力舉例會很 而且電腦連續開20個小時可能還沒出來)
下面得作法在ZeroJudge開不暸會RE 請在自己的電腦估算
發現算出來的數字分解後 質因數不超過5萬
要修改加快 請自行修改
/********************5分鐘以內******************************/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int math[15200000]={0};
char make[200000000]={0};
main()
{
int n,a,b,c,m=1;
math[0]=2;
for(b=2;b<200000000;b=b+2)
make[b]++;
for(a=3;a<10000000;a=a+2)/*5W*5W已經2.5E 無須建更大*/
{
int flag=0;
for(b=0;math[b]<=sqrt(a)&&b<=m;b++)
{
if(a%math[b]==0)
{
flag=1;
break;
}
}
if(flag==0)
{
math[m]=a;
for(b=a;b<200000000;b=b+a)
make[b]++;
m++;
}
}
int time=0;
for(a=0;a<200000000;a++)
{
if(make[a]==5) time++;
else time=0;
if(time==5) {printf("%d\n",a-4);break;}
}
system("pause");
}
/*******************************************************/
#include<stdio.h>
#include<stdlib.h>
main()
{
printf("129963314\n");
return 0;
}
上一篇:Problem 47
下一篇:加法減法的奧妙