F  素数划分
Time Limit:1000MS  Memory Limit:65535K
题型: 编程题   语言: 无限制
描述
给定一个最多不超过30个字符的数字字符串（只由0到9，十个数字构成），如果将该字符串切割成
多段（每一段数字不超过6个字符），如果能找到一种划分使每一段构成的数字都是质数，则输出“YES”
，怎么也找不到，输出“NO”。
例如
1447160917891993
可以划分为
1447 1609 17 89 199 3
均为质数，输出YES

再例如
999444
输出NO

bool foo( const char* s )
{
    if( s前6位是素数 && foo(s+6) )
        return true;
    if( s前5位是素数 && foo(s+5) )
        return true;
    if( s前4位是素数 && foo(s+4) )
        return true;
    if( s前3位是素数 && foo(s+3) )
        return true;
    if( s前2位是素数 && foo(s+2) )
        return true;
    if( s前1位是素数 && foo(s+1) )
        return true;
    return false;
}

收到的鲜花

• 搬砖 于 2016-12-16 16:08 送鲜花  1朵   附言：好文章

可不可以用c写一下，或者写一下题解，新手不是很懂

#include <stdio.h>
#include <stdbool.h>

bool isprime( unsigned n ) // 这个写得很烂，只是演示
{
    if( n < 2 )
        return false;
    if( n == 2 )
        return true;
    if( n%2 == 0 )
        return false;

    for( unsigned i=3; i*i<=n; i+=2 )
        if( n%i == 0 )
            return false;
    return true;
}

bool foo( const char* s )
{
    if( !*s ) return true;

    for( int i=0; s[i]; ++i )
    {
        char format[20];
        sprintf( format, "%%%du", i+1 );

        unsigned n;
        sscanf( s, format, &n ); // 上面四行也很烂，只是为了演示

        if( isprime(n) && foo(s+i+1) )
        {
            printf( " %0*u", i+1, n );
            return true;
        }
    }
    return false;
}

int main( void )
{
    foo( "1447160917891993" );
    // foo( "999444" );
}

我太蠢了，c++不懂

不如你写一下题解，我自己来敲代码

解题关键是抓住字符串的连续性，找到上一个素数，下一个素数判断点在上一个素数末尾之后，建立六位数的素数表会不会快一点呢~遍历求素数长度的条件是从低位到高位，有点想到用栈空间，满足条件的进栈，搜索到字符串尽头依然没有满足条件的就出栈~有点像迷宫算法，递归也可以考虑~

[此贴子已经被作者于2016-12-16 19:13编辑过]

我只会打表，栈还没学，问题在于我怎么划分素数，用深度搜索？

我的想法是判断到素数就停止，后来写出来发现不妥，有bug

新人发表一下浅见:
1.把6位数以下的素数全找出来,放到一个文件里头去;
2.编辑
boolean foo(char *s){
  int i,num;
  for(i;i<=6;i++){
    num=s[0-i]组成的数字;
    if ( num能在pri.txt中找到 ){
      if ( s还没完 ){
        foo(s剩下的部分);
      }
      else  return true;
    }
    else continue;
  }
  //能运算到这里来,也就是没有运行return true
  return false;
}