整数序列问题

无心人

有整数序列$n_i$，长度为$k$

如果对任何素数$p_j <= k$满足
    按顺序从序列数出第$p_j$个数字$n_i$，如果长度不够，
    则从序列首位置接着数，数到的整数移出序列
    移出后，序列自动紧缩，循环处理直到序列为空
    将移出序列的数字顺序写在一起，如果是素数，称为满足条件。

比如，有长度为10的序列，以位置表示：
    则p = 2  2 4 6 8 10 3 7 1 5 9位置数字连在一起
       p = 3  3 6 9 2 7 1 8 5 10 4位置数字连在一起
       p = 5  5 10 6 2 9 8 1 4 7 3位置数字连在一起
       p = 7  7 4 2 1 3 6 10 5 8 9位置数字连在一起
均是素数，则满足条件
      
现在求$k = 16$的对应的满足上述条件的一个序列的例子

mathe

我先限定序列中都是一位数（可以是0，但是0不能是任何整数第一个位置），那么k=16可以找到的部分解:
1110111101597989
1110111101976316
1110111104676694
1110111107733380
1110111109136435
1110111115232258
1110111117413084
...

mathe

1. 
   
2. #if 1
   
3.     #define _Test_HI
   
4.     #define integer CHugeInt
   
5. #else
   
6.     #define _Test_HX
   
7.     #define integer CHugeIntX
   
8. #endif
   
9. #define K 16
   
10. #define NP 6 //Total 6 primes less than K: 2,3,5,7,11,13
    
11. int plist[NP]={2,3,5,7,11,13};
    
12. int order[NP][K];
    
13. int ntype[K];
    
14. #define HEAD 1
    
15. #define TAIL 2
    
16. 
    
17. void init_order()
    
18. {
    
19.     int orig[K];
    
20.     int i;
    
21.     for(i=0;i<NP;i++){
    
22.         int j;
    
23.         int c=0,s;
    
24.         for(j=0;j<K;j++)orig[j]=j;
    
25.         for(c=0,s=-1;c<K;c++){
    
26.             int d=0;
    
27.             for(d=0;d<plist[i];d++){
    
28.                 s++;if(s>=K)s=0;
    
29.                 while(orig[s]==-1){s++;if(s>=K)s=0;}
    
30.             }
    
31.             order[i][c]=orig[s];
    
32.             orig[s]=-1;
    
33.         }
    
34.         ntype[order[i][0]]|=HEAD;
    
35.         ntype[order[i][K-1]]|=TAIL;
    
36.     }
    
37. }
    
38. int tvalue[]={1,3,7,9};
    
39. 
    
40. bool next_valid(int buf[K])
    
41. {
    
42.     int i;
    
43.     for(i=K-1;i>=0;i--){
    
44.         if(buf[i]==9){
    
45.             buf[i]=0;
    
46.         }else{
    
47.             buf[i]++;
    
48.             break;
    
49.         }
    
50.     }
    
51.     if(i<0)return false;
    
52.     for(i=0;i<K;i++){
    
53.         if(ntype[i]&TAIL){
    
54.             if((buf[i]&1)==0){
    
55.                 buf[i]++;
    
56.             }
    
57.             if(buf[i]==5)buf[i]=7;
    
58.         }else if(ntype[i]&HEAD){
    
59.             if(buf[i]==0){
    
60.                 buf[i]=1;
    
61.             }
    
62.         }else{
    
63.         }
    
64.     }
    
65.     return true;
    
66. }
    
67. 
    
68. int main(int argc, char* argv[])
    
69. {
    
70.     integer u;
    
71.     int c=0,i;
    
72.     int buf[K];
    
73.     init_order();
    
74.     for(c=0;c<K;c++)buf[c]=0;
    
75.     do{
    
76.         int j;
    
77.         if(!next_valid(buf))break;
    
78.         for(i=0;i<NP;i++){
    
79.             u=0;
    
80.             for(j=0;j<K;j++){
    
81.                 u*=10;u+=buf[order[i][j]];
    
82.             }
    
83.             if(!u.IsPrime()){
    
84.                 break;
    
85.             }
    
86.         }
    
87.         if(i==NP){
    
88.             for(c=0;c<K;c++){
    
89.                 printf("%d",buf[c]);
    
90.             }
    
91.             printf("\n");
    
92.         }
    
93.     }while(1);
    
94.     return 0;
    
95. }
    

复制代码

mathe

在让程序将前两个序列对应所有素数给输出：
1110111101597989
        1011199911581701
        1109811591709111
        1180511901971191
        1917191011108159
        5118799111100911
        7111099085911111
1110111101976316
        1011173611911601
        1107111961603111
        1110911601361171
        1316161011101197
        9111673111100611
        6111076019311111

无心人

增加点难度？？
可以否？

要求序列每个整数都不同

mathe

应该还好，那就是需要使用两位数，复杂度可能会稍微提高一些，但是没有什么本质区别。
我觉得应该可以直接使用1~16去构造

无心人

不可能吧

需要打乱顺序吧

否则无法保证末尾是1，3，7，9

mathe

我的程序就是通过先判断哪几个数必须末尾是1,3,7,9来提高效率的。
唯一的区别就是这个程序写起来更加讨厌一些。

无心人

你不强求是1－－16就好了

无心人

要不就干脆来更惊险的

1--n
从2到n均执行我说的操作

要求全素数

这个没解的概率大