隐藏的密码 ACM中的竞赛题

Question

竞赛题
G 隐藏的密码
Time Limit:1000MS Memory Limit:65535K
题型: 编程题 语言: 无限制
描述
一个神密的密码隐藏在一个正整数N当中（1<N<10的8次方），该密码是N中一段连续的数字且这段数字构成的数是一个质数，
如果存在多个，则正确的密码是数值最大的一个（数值前不含无效的零），请编程输入正整数N，找出正确的密码并输出。
如果N中不存在满足题意的密码，则输出invalid
例如：输入
44
输出
invalid

输入格式
一个正整数N（1<N<10的8次方）
输出格式
满足题意的密码
输入样例
13292
输出样例
29
Provider admin

Answer 1

#include <stdio.h>
#include <windows.h>
#include <math.h>

bool IsPrime(unsigned n)  
{  
    if (n<2)  
    {
        return false;  
    }  
    for(unsigned i=2;i<n/2+1;++i)  
    {   
        if ( 0 == n % i )  
        {   
            return false;  
        }  
    }  
    return true; 
}

void main()
{
    int num = 0;
    printf("Input number:\n");
    scanf("%d",&num);

    unsigned long starts, stop;
    starts = GetTickCount();


    int a[8]={0};
    int result = 0;
    int j = 0;


    int mynum = 0;
    int k=0;

    for (int i=7;i>=0;i--)
    {
        a[i] = num%10;
        num = num/10;
        j++;
        if (num==0)
        {
            break;
        }

    }

    int start = i;
    for (int n=j;n>0;n--)
    {
        for (int mm = 0;mm<j-n+1;mm++)
        {
            mynum = 0;
            k = 0;
            for (int ss = 0;ss<n;ss++)
            {
                mynum = mynum*10+a[mm+start+k];
                k++;
            }
            if (IsPrime(mynum))
            {
                if (result==0)
                {
                    result = mynum;
                }
                else
                {
                    if(mynum>result)
                        result = mynum;
                }

            }
        }
        if (result!=0)
        { 
            int ddd = result/pow(10,n-1);
            if(ddd !=0)
            {
                printf("%d\n",result);
                break;
            }
            else
                continue;
        }

    }

    if (result == 0)
        printf("invalid\n");
    stop = GetTickCount();
    printf("time: %lld ms\n", stop - starts);
}