帅地
2017-03-15 11:25
采纳率: 50%
浏览 1.4k
已采纳

隐藏的密码 ACM中的竞赛题

竞赛题
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

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

1条回答 默认 最新

  • 伪造的时空 2017-03-15 13:52
    最佳回答
    #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);
    }
    
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题