整数序列问题

无心人

有整数序列$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

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
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};
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. }
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均执行我说的操作 要求全素数 这个没解的概率大