升序素数和降序素数
如果一个素数的十进制表示每个数位写成一个序列，其值是升序排列，则叫升序素数否则叫降序素数
比如
1123 1129就是升序素数
54311就是降序素数
现在求100000000内的该类素数 范围太小了吧,10^8内单调的数只有C(10+8-1,8)=C(17,9)=24310个,只要列举出这24310个数,再判素就ok了,应该可以在1秒内出解.
把范围改大一点才比较有难度,比如,改成10^25. :)
那考虑$10^32$以内的吧 10^32内的单调数个数有C(32+10-1,32)=C(41,9)=350343565个.
我这边产生这350343565个数对应的组合大概要7秒,再由这些组合得到单调数.
再用Miller-Rabin测试判素,这些过程加起来,大概要半个钟头.
也可以做一些筛选,比如可以快速判断某个组合对应的单调数是否被小素数2,3,5,7,11整除,这样的筛选,大概可以将用Miller-Rabin测试判素的数减少5倍左右.
另外,可以取前N个素因子的乘积S,再对某个单调数a以gcd(S,a)来筛选,以减少Miller-Rabin判素算法的调用次数.
还有一种基于hash技术的做法,把32位分成两半,这样每一半只有C916+10-1,16)=C(25,9)=312455,这样每个单调数可表示为:xi*10^16+xj (xj的首数字大于xi的末数字),不过我没想到什么好办法来筛选,如果解决了这个问题,应该可以较大幅度地提高速度. :)
可以考虑优化了 写了个小程序算了一下10^20内的降序素数,有488441个候选(只做了一次Miller-Rabin测试).输出文件有9M多,发不上来.
发一个10^15内的降序候选素数表. :)
你用PRIMO证明下
程序在我的那个素性和分解的帖子里
哈哈
估计要耗费100小时证明这么多素数 发一下代码:#include <windows.h>
#include <stdio.h>
#include "gmp.h"
FILE *pf=fopen("data.txt","w");
const intL=8;
int count=3;
unsigned prime[]={
7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,
179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,
419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,
547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,
811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,
947,953,967,971,977,983,991,997
};
unsigned p_prime[]={
7,11,31,41,43,53,61,71,73,83,97,211,311,331,
421,431,433,443,521,541,557,631,641,643,653,
661,733,743,751,761,773,811,821,853,863,877,
881,883,887,911,941,953,971,977,983,991,997
};
mpz_t Hash, Prime_Product, com_factor;
void Init( ){
int i, j;
for( i=0; i<10; ++i ){
for( j=0; j<L; ++j )
mpz_init_set_ui( Hash, (i==0)? 0 : i );
}
for( i=1; i<10; ++i ){
for( j=1; j<L; ++j )
mpz_mul_ui( Hash, Hash, 10 );
}
mpz_init_set_ui( Prime_Product, 1 );
mpz_init( com_factor );
for( i=0; i<sizeof(prime)/sizeof(prime); ++i )
mpz_mul_ui( Prime_Product, Prime_Product, prime );
}
void Clear( ){
mpz_clear( Prime_Product );
mpz_clear( com_factor );
for( int i=0; i<10; ++i ){
for( int j=0; j<L; ++j )
mpz_clear( Hash );
}
fclose( pf );
}
void Specail_Print(){
fprintf(pf,"2\n3\n5\n");
for( int k=0; k<sizeof(p_prime)/sizeof(p_prime); ++k )
fprintf(pf,"%u\n",p_prime), ++count;
}
void combination( int n, int m ){
mpz_t num;
mpz_init_set_ui( num, 0 );
unsigned*c=new unsigned, j, dig_sum=m;
for( j=1; j<=m; ++j )c=j-1, mpz_add( num, num, Hash );
c=n;
R2:
if( c%2==0 && c+1!=5 && dig_sum%3!=0 ){
mpz_gcd( com_factor, num, Prime_Product );
if( mpz_cmp_ui( com_factor, 1 )==0 && mpz_probab_prime_p( num, 1 ) ){
mpz_out_str( pf, 10, num );
fprintf(pf,"\n");
++count;
}
}
if( m&1 )
if( c+1<c ){
++c;
mpz_add_ui( num, num, 1 );
++dig_sum;
goto R2;
}
else{
j=2;goto R4;
}
else
if( c>0 ){
--c;
mpz_sub_ui( num, num, 1 );
--dig_sum;
goto R2;
}
else{
j=2;goto R5;
};
R4:if( c>=j ){
if( j<=m )
mpz_sub( num, num, Hash-j+2] ), dig_sum-=c-j+2;
if( j-1<=m )
mpz_sub( num, num, Hash-j+3] ), dig_sum-=c-j+3;
c=c;
c=j-2;
if( j<=m )
mpz_add( num, num, Hash-j+2] ), dig_sum+=c-j+2;
if( j-1<=m )
mpz_add( num, num, Hash-j+3] ), dig_sum+=c-j+3;
goto R2;
}
else
++j;
R5:if( c+1<c ){
if( j<=m )
mpz_sub( num, num, Hash-j+2] ), dig_sum-=c-j+2;
if( j-1<=m )
mpz_sub( num, num, Hash-j+3] ), dig_sum-=c-j+3;
c=c;
c=c+1;
if( j<=m )
mpz_add( num, num, Hash-j+2] ), dig_sum+=c-j+2;
if( j-1<=m )
mpz_add( num, num, Hash-j+3] ), dig_sum+=c-j+3;
goto R2;
}
else{
++j;
if( j<=m ) goto R4;
}
delete []c;
mpz_clear( num );
}
int main(int argc, char *argv[])
{
Init( );
Specail_Print( );
int time=GetTickCount();
for( int i=4; i<=L; ++i )
combination( i+8,i);
Clear( );
printf("total : %d\n",count);
printf("%d ms\n",GetTickCount()-time);
return 0;
} 另外,如果要验证我在6#给的数据是否全是素数,可以采用特殊底的Miller-Rabin测试,底只需要取成2,3,7,61,24251这几个素数就可以了.
我已经用上面的方法对6#的数据做了全面的验算,表中的数据全部都是素数. :)
效果不错
程序啰嗦
哈
页:
[1]
2