10789-Prime Frequency

<br /> /* <br /> "Prime Frequency"<br /> Level:3.0<br /> Date:2006/9/25<br /> <br /> 技巧: 製作一質數表, mask掉出現過的完元, bubble sort質數set. <br /> */<br /> <br /> #include <stdio.h><br /> #include <string.h><br /> #define N 2001<br /> #define MAX_CHAR 256<br /> int prime[303]={0};<br /> <br /> void getPrime(void);<br /> <br /> main(){<br /> int n=0,round=1,len=0,i=0,j=0,k=0,z=0,count=0;<br /> char temp;<br /> char input[N+1]={}; <br /> char set[MAX_CHAR]={}; //記錄出現的字元集合set. <br /> bool check[N+1]={false};<br /> getPrime();<br /> scanf("%d",&n);<br /> while(n-- > 0 ){<br /> scanf("%s",&input);<br /> len = strlen(input);<br /> printf("Case %d: ",round++);<br /> for(i=0;i < len;i++){ if(check[i]) //被mask掉的字元,便跳過不檢查. continue; temp=input[i]; count=1; for(j=i+1;j < len;j++){ if(temp==input[j]){ check[j]=true; //將相同的字元mask掉. count++; //累計字元出現的次數. } } while(count >= prime[k]){<br /> if(count == prime[k++]){ //如果字元出現次數是質數,便加入set.<br /> set[z++] = input[i];<br /> } <br /> }<br /> k=0; <br /> }<br /> set[z]='\0';<br /> if(*set == '\0'){<br /> printf("empty\n");<br /> }<br /> else{<br /> len = strlen(set);<br /> for(i=0;i < len;i++){ //依ASCII做bubble sort. for(j=i+1;j < len;j++){ if(set[i] > set[j]){<br /> temp = set[i];<br /> set[i]=set[j];<br /> set[j]=temp;<br /> } <br /> } <br /> } <br /> for(i=0;i < len;i++){ printf("%c",set[i]); } set[z=0]='\0'; printf("\n"); } for(i=0;i < N;i++) check[i]=false; } } void getPrime(void){ int n[N+1]={0},i=0,j=0; for(i=2;i*i <= N;i++){ for(j=i*2;j <= N;j++){ if(j%i == 0) n[j]=1; // 1,if n[j] is not a prime. } } j=0; for(i=2;i < N;i++){ if(n[i] == 0){ prime[j++] = i; //Collect all of prime. } } }