迭代.不妨称所求的数为sprime数.
利用sprime数的性质,i位的sprime数,前i-1位必然也是sprime数.而未尾一位只可能是1,3,7,9 四个数之一
一位的sprime数可以很容易的就知道:2,3,5,7
而二位的sprime数可以在一位的sprime数未尾试探加上一个尾数(1,3,5,7)变成一个新数num
若num为素数则存入数组result[],最后对result[]排序即可
为了方便输出可以记下result[]中一位数,两位数,三位数…..的开始下标
源码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | /* ID: tgh7281 LANG: C++ TASK: sprime */ #include <iostream> #include <fstream> #include <cmath> using namespace std; int cmp(const void*a,const void*b); bool isprime(int number); int main() { ifstream fin("sprime.in"); ofstream fout("sprime.out"); int result[100]={2,3,5,7},tail[4]={1,3,7,9}; //根据测试结果,result[]大小不超过90,最开始我开了1W大小 int start[10]={0,0,4}; //分别表示长度为1..8的序列在结果数组的开始下标,第0个位置不用 int number,i,j,k,total=4; for (i=2;i<=8;i++) //每一轮循环生成长度为i的所有sprime number { for (j=start[i-1];j<start[i];j++) { for (k=0;k<4;k++) { number=result[j]*10+tail[k]; if (isprime(number)) { result[total++]=number; } } } start[i+1]=total; } int n; fin>>n; qsort(result,total,sizeof(result[0]),cmp); for (i=start[n];i<start[n+1];i++) fout<<result[i]<<endl; fin.close(); fout.close(); return 0; } int cmp(const void*a,const void*b) { return *((int*)a)-*((int*)b); } bool isprime(int number) { for (int i=2;i<=sqrt(number);i++) if (number%i==0) return false; return true; } |
1,025 views