C语言简单算法-看来的，小弟我是搞不定啊

C语言简单算法--看来的，我是搞不定啊。。。
题目详情
如果一个数各个数位上的数字之和是质数，并且各个数位上的数字的平方和也是质数，则称它为幸运数。
给定x，y，求x，y之间（ 包含x，y，即闭区间[x,y]）有多少个幸运数。

例如1到20之间有4个幸运数，它们是11,12,14,16，像因为1+1 = 2是质数，1^2 + 1^2 = 2也是质数等等。
给定函数原型，其中1<=x<=y<=1000000000，请完成函数，实现上述功能。

答题说明
运行时间限时3秒。 算法 C
[解决办法]

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int CheckIsP(int aNum)
{
    if (aNum == 2)
    {
        return 1;
    }

    if (aNum == 1)
    {
        return 0;
    }

    int i;
    for (i=2;i<aNum;i++)
    {
        if ((aNum % i) == 0)
        {
            return 0;
        }

        if (i >= (aNum / 2))
        {
            break;
        }
    }
    return 1;
}

int CheckNUM(int aNum)
{
    int NumDigCount;
    char pNum[20];
    itoa(aNum,pNum,10);
    NumDigCount = strlen(pNum);

    int i,tmpDig;
    int DigSum=0;
    int DigSqSum=0;
    for (i=0;i<NumDigCount;i++)
    {
        tmpDig = pNum[i] - '0';
        DigSum += tmpDig; 
 
        DigSqSum += tmpDig * tmpDig;
    }

    if ((CheckIsP(DigSum) == 1) &&(CheckIsP(DigSqSum) == 1))
    {
        return 1;
    }

    return 0;
}

int main()
{
    int X,Y;
    int i;
    printf("请先输入(X，Y)!\n");
    scanf("%d,%d",&X,&Y);
    for (i = X; i <= Y; i++)
    {
        if (CheckNUM(i) == 1)
        {
            printf("%d \n",i);
        }
    }

    char E;
    printf("按任意键退出系统！\n");
    scanf("%c",&E);
    return 0;
}

[解决办法]

引用:

Quote: 引用:

x=1,y=10亿可以在3秒内算出来，但x，y不确定的时候就。。。

求代码，求真相

10亿显然不是幸运数，只考虑[1,10亿-1]，9位数字，可以相当于长度为9的字符串（不满9位的高位取0），每个位置上可选0-9,10个数字，他们的和最大是9*9=81，所以首先在2-81找出所有满足条件的质数，得出这些是指数的和之后进行拆分，看给定和时9个数字分别需要多少个，多少个0，多少个1，...，多少个9，过滤其中平方和不满足条件的个数组合，然后对每个组合做排列组合，就可以得出1-10亿有多少个幸运数了，我已经实现了，2秒左右跑完，但纠结的是好像不能用这种方法快速定位任意[x,y]区间内的幸运数数。求指导。
[解决办法]
@lengyuehui  @Mr_Ringht 

x<y<=1000000000  ,各数字之和为质数 ，各数位数字的平方之和为质数。可以先通过筛选法求出Y范围内的素数 。

9个数位 ，所以加起来的和最多为81  ，平方加起来和最多为810 ，所以，你可以通过筛选法先求出1-810之间的素数。
然后把这些素数存储起来 。后面输入的数字，直接判断处理之后的结果在不在这个素数数组中就可以得出结果。话说这个不用花很多时间 。但是把他定义为全局数组，在主函数中调用，不起作用。不知道怎么回事。
[解决办法]

#include <stdio.h>

#define MaxDigit 10
#define MaxPrime (MaxDigit * 9 * 9)
int notprime[MaxPrime+1];
int pow10v[MaxDigit] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
int fact[MaxDigit+1];
#define isprime(i) (!notprime[i])
void init(void);
int solve(int x);
int solve_section(int past1, int past2, int digits); 
 
int solve_rec(int past1, int past2, int digits, int curdigit, int perm);
int main(void)
{
int a, b;
init();
while(scanf("%d%d", &a, &b) == 2)
printf("%d\n", solve(b) - solve(a-1));
return 0;
}
void init(void)
{
int i, j;
notprime[0] = notprime[1] = 1;
for(i=2;i<=MaxPrime;i++)
{
if(notprime[i])
continue;
for(j=i*i;j<=MaxPrime;j+=i)
notprime[j] = 1;
}
for(i=fact[0]=1;i<=MaxDigit;i++)
fact[i] = fact[i-1] * i;
}
int solve(int x)
{
int digits, curdigit, result = 0, curpast1 = 0, curpast2 = 0;
for(digits=MaxDigit-1;digits>=0;digits--)
for(curdigit=0;curdigit<10;curdigit++)
{
if(x < pow10v[digits])
{
curpast1 += curdigit;
curpast2 += curdigit * curdigit;
break;
}
result += solve_section(curpast1 + curdigit, curpast2 + curdigit * curdigit, digits);
x -= pow10v[digits];
}
return result;
}
int solve_section(int past1, int past2, int digits)
{
return solve_rec(past1, past2, digits, 9, fact[digits]);
}
int solve_rec(int past1, int past2, int digits, int curdigit, int perm)
{
int result = 0, i;
if(curdigit == 0 
[解决办法]
 digits <= 0)
return isprime(past1) && isprime(past2) ? perm / fact[digits] : 0;
for(i=0;i<=digits;i++)
result += solve_rec(past1 + i*curdigit, past2 + i*curdigit*curdigit, digits-i, curdigit-1, perm / fact[i]);
return result;
}

fancymouse@fancymouse-vm:/tmp$ gcc a.c -O3
fancymouse@fancymouse-vm:/tmp$ time echo 1 1000000000 
[解决办法]
 ./a.out
85804914

real0m0.033s
user0m0.020s
sys0m0.030s
fancymouse@fancymouse-vm:/tmp$

查看更多 下一篇