001 #include <string.h>
002 #include <stdio.h>
003 #include <stdlib.h>
004 #include <math.h>
005 #include <time.h>
006
007 int isPrime(unsigned int number)
008 {
009     unsigned int i;
010     if (number<2) return 0;
011     if (number!=2 && number%2==0) return 0;
012     for(i=3;i<=floor(sqrt(number));i+=2) if ((number % i) == 0) return 0;
013     return 1;
014 }
015
016 void dumpArrayLong(unsigned int *array,int length)
017 {
018     int i;
019     for(i=0;i<length;i++) printf("%u ",array[i]);
020     printf("\n");
021 }
022
023 void dumpArrayInt(int *array,int length)
024 {
025     int i;
026     for(i=0;i<length;i++) printf("%d ",array[i]);
027     printf("\n");
028 }
029
030 unsigned int calNumber(int *myArr,unsigned int *numberArr,int length)
031 {
032     unsigned int i;
033     long result=0;
034     for(i=0;i<length;i++) result+=(myArr[i]-1)*numberArr[i];
035     return result<0?-result:result;
036 }
037
038 int dumpLink(char*inStr)
039 {
040     char *p;
041     int cnt=0;
042   
043     for ( p=inStr; *p!=0; p ++)
044     {
045         cnt+=((*p)==';');
046     }
047     return cnt;
048 }
049
050 int combination(unsigned int **intArr,unsigned int m,unsigned int n)
051 {
052     int i,index;
053     if ((*intArr)==NULL)
054     {
055         (*intArr)=(unsigned int *)malloc(m*sizeof(unsigned int));
056         for(i=0;i<m;i++) (*intArr)[i]=i+1;
057         return 1;
058     }
059     index=m-1;
060
061     while(n-(*intArr)[index]<=m-index-1 && index>=0)
062     {
063         index--;
064     }
065     if (index>=0)
066     {
067         for(i=index;i<m;i++)
068         {
069             (*intArr)[i]++;
070             if(i<m-1) (*intArr)[i+1]=(*intArr)[i];
071         }
072         return 1;
073     }
074     free((*intArr));
075     (*intArr)=NULL;
076     return 0;
077 }
078
079 int seekStatus(char **skdStr,unsigned int inInt)
080 {
081     char *tmp;
082     char intStr[20];
083     int len;
084     sprintf(intStr,"%u;",inInt);
085     if (*skdStr==NULL)
086     {
087         len=(strlen(intStr)+2)*sizeof(char);
088         (*skdStr)=(char *)malloc(len);
089         strcpy(*skdStr,intStr);
090         return 1;   
091     }
092     if (strstr((*skdStr),intStr)!=NULL) return 0;
093    
094     len=(strlen(*skdStr)+strlen(intStr)+2)*sizeof(char);
095     tmp=(char *)malloc(len);
096     strcpy(tmp,*skdStr);
097     free(*skdStr);
098     (*skdStr)=tmp;
099     tmp+=strlen(*skdStr);
100     strcpy(tmp,intStr);
101     return 1;
102 }
103
104 int powerN(int **intArr,int n,int p,int start)
105 {
106     int i,index;
107     if ((*intArr)==NULL)
108     {
109         (*intArr)=(int *)malloc(n*sizeof(int));
110         for(i=0;i<n;i++) (*intArr)[i]=start;
111         return 1;
112     }
113     index=0;
114     (*intArr)[index]++;
115     while((*intArr)[index]>=start+p && index<n)
116     {
117         (*intArr)[index++]=start;
118         if (index<n) (*intArr)[index]++;
119     }
120     if (index<n) return 1;
121    
122     free((*intArr));
123     (*intArr)=NULL;   
124     return 0;
125 }
126
127 void dumpArrayLong2String(unsigned int *array,int length,char **inStr)
128 {
129     int i;
130     char *p;
131     p=*inStr;
132     (*inStr)[0]=0;
133     for (i=0;i<length;i++)
134     {
135         sprintf( p, "%u ",array[i] );
136         while((*p)) p++;
137     }
138 }
139
140 int main()
141 {
142     int *signs=NULL;
143     unsigned int *numbers=NULL;
144     unsigned int Number,Max_Int=100;
145     char *PrimeQue=NULL;
146     clock_t start,end;
147     unsigned int *results=NULL;
148     int i,j,flag;
149     unsigned int tmp,index,Max_Num;
150     for (Number=3;Number<=14;Number++)
151     {
152         start=clock();
153         if (results!=NULL) free(results);
154         results=(unsigned int *)malloc(Number*sizeof(unsigned int));
155         Max_Num=0;
156         while (combination(&numbers,Number,Max_Int))
157         {
158                 tmp=0;
159                 for(i=0;i<Number;i++) tmp|=numbers[i];
160                 if (PrimeQue!=NULL)
161                 {
162                     free(PrimeQue);
163                     PrimeQue=NULL;
164                 }
165                 index=0;
166                 flag=1;
167                 while(powerN(&signs,Number,3,0))
168                 {
169                     tmp=calNumber(signs,numbers,Number);
170                     if (isPrime(tmp))
171                     {
172                         if (seekStatus(&PrimeQue,tmp) && flag) flag=0;
173                     }
174                 }
175                 if (!flag)
176                 {
177                     tmp=dumpLink(PrimeQue);
178                     if (tmp>Max_Num)
179                     {
180                         for(i=0;i<Number;i++) results[i]=numbers[i];
181                         Max_Num=tmp;
182 //                        printf("Number N:%d Max prime numbers is %d.\n---------------------------------------------\n",Number,Max_Num);
183 //                        dumpArrayLong(results,Number);
184 //                        printf("---------------------------------------------\n\n");
185 //                        end=clock();
186 //                        printf("Number calculation took %lf sec.\n\n",(double)(end-start)/(double)CLOCKS_PER_SEC);
187                     }
188                 }
189         }
190         free(numbers);
191         numbers=NULL;
192         printf("Number N:%d Max prime numbers is %d.\n=======================================\n",Number,Max_Num);
193         dumpArrayLong(results,Number);
194         printf("=======================================\n");
195         end=clock();
196         printf("Number calculation took %lf sec.\n\n",(double)(end-start)/(double)CLOCKS_PER_SEC);
197     }
198     return 0;
199 }