[C][瘋狂程設][CPE考題20150625] 15C3.UVA406：Prime Cuts

Prime Cuts

A prime number is a counting number ( tex2html_wrap_inline26 ) that is evenly divisible only by 1 and itself. In this problem you are to write a program that will cut some number of prime numbers from the list of prime numbers between (and including) 1 and N. Your program will read in a number N; determine the list of prime numbers between 1 and N; and print the C*2 prime numbers from the center of the list if there are an even number of prime numbers or (C*2)-1 prime numbers from the center of the list if there are an odd number of prime numbers in the list.

Input

Each input set will be on a line by itself and will consist of 2 numbers. The first number ( tex2html_wrap_inline38 ) is the maximum number in the complete list of prime numbers between 1 and N. The second number ( tex2html_wrap_inline42 ) defines the C*2 prime numbers to be printed from the center of the list if the length of the list is even; or the (C*2)-1 numbers to be printed from the center of the list if the length of the list is odd.

Output

For each input set, you should print the number N beginning in column 1 followed by a space, then by the number C, then by a colon (:), and then by the center numbers from the list of prime numbers as defined above. If the size of the center list exceeds the limits of the list of prime numbers between 1 and N, the list of prime numbers between 1 and N (inclusive) should be printed. Each number from the center of the list should be preceded by exactly one blank. Each line of output should be followed by a blank line. Hence, your output should follow the exact format shown in the sample output.

Sample Input

21 2
18 2
18 18
100 7

Sample Output

21 2: 5 7 11↵\r\n
↵\r\n
18 2: 3 5 7 11↵\r\n
↵\r\n
18 18: 1 2 3 5 7 11 13 17↵\r\n
↵\r\n
100 7: 13 17 19 23 29 31 37 41 43 47 53 59 61 67↵\r\n
↵\r\n

注意事項:

1.讀取資料輸入直到結束

 int max,amount;

 while(scanf("%d %d",&max, &amount)!=EOF){
        ...
        }

2.找出範圍內的質數(題目定義質數包含1)，並將這些質數存放在array當中

  int prime[max];
  prime[1]=1;
  prime[2]=2;
  count=2;
 
  //find the prime list
  for(int num=3;num<=max;num+=2){
   is_prime=1;
   for(int j=2;j<num;j++){
    if((num%j)==0 && (j!=num)){
     is_prime=0;
     break;
    }
   }
   if(is_prime){
    count++;
    prime[count]=num;
   }
  }

3.找出要需要列印出來的質數的位置:

  if(count%2==0){
   center = count/2;
   start = center-amount+1;
   end = center+amount;
  }else{
   center = count/2+1;
   start = center-amount+1;
   end = center+amount-1;
  
  }

4.若是要列印出來的質數數量超過範圍讀處理方式:

  if(start<=0)start=1;
  if(end>=count)end=count;

5.將題目所需要的質數列印出來:

  for(int k=start;k<=end;k++){
    printf(" %d",prime[k]);
  }

Code:

#include <stdio.h>
#include <math.h>

int main(void){

 int max,amount;

 while(scanf("%d %d",&max, &amount)!=EOF){
 
  int prime[max];
  printf("%d %d:",max,amount);
 
  for(int i=1;i<max;i++){
   prime[i]=0;
  }
  
  int is_prime,count;
  int start,center,end;
 
  prime[1]=1;
  prime[2]=2;
  count=2;
 
  //find the prime list
  for(int num=3;num<=max;num+=2){
   is_prime=1;
   for(int j=2;j<num;j++){
    if((num%j)==0 && (j!=num)){
     is_prime=0;
     break;
    }
   }
   if(is_prime){
    count++;
    prime[count]=num;
   }
  }
  //for(int  l=1;l<=count;l++) printf("%d.%d\n",l,prime[l]);

  //check the how many and the site to print out.
  if(count%2==0){
   center = count/2;
   start = center-amount+1;
   end = center+amount;
  }else{
   center = count/2+1;
   start = center-amount+1;
   end = center+amount-1;
  
  }
  
  //for the exception situations
  if(start<=0)start=1;
  if(end>=count)end=count;
  
  //show the result
  for(int k=start;k<=end;k++){
    printf(" %d",prime[k]);
  }
  //printf(",count=%d,center=%d,start=%d,end=%d",count,center,start,end);
  printf("\n\n");
 }
 
 return 0;
}

[C][瘋狂程設][CPE考題20150625] 15C2.UVA10931:Parity

Problem E - Parity

Time Limit: 1 second We define the parity of an integer n as the sum of the bits in binary representation computed modulo two. As an example, the number 21 = 101012 has three 1s in its binary representation so it has parity 3 (mod 2), or 1. In this problem you have to calculate the parity of an integer 1 ≤ I ≤ 2147483647.

Input

Each line of the input has an integer I and the end of the input is indicated by a line where I = 0 that should not be processed.

Output

For each integer I in the inputt you should print a line The parity of B is P (mod 2)., where B is the binary representation of I.

Sample Input

1 2 10 21 0

Sample Output

The parity of 1 is 1 (mod 2).
The parity of 10 is 1 (mod 2).
The parity of 1010 is 2 (mod 2).
The parity of 10101 is 3 (mod 2).

注意事項

1.讀取資料到字元0:

 int input;
 scanf("%d",&input);
 while(input!=0){....}

2.利用 link list 的結構，宣告指標，儲存2進位數字:

 char *data;
 count=0;
 *(data+count)=num%BASE;

3.數字10進位轉2進位，並且將結果儲存到data:

while(num>0){
 int i=num%BASE;
 *(data+count)=num%BASE;
 count++;
 num = num/BASE;
}

並且輸出結果:

for(int j=count-1;j>=0;j--){
 printf("%d",*(data+j));
}

4.計算parity位數:

 (i==1) ? (parity+=1) : (parity+=0);

Code:

#include <stdio.h>

#define BASE 2

int main(void){

 int input,num,parity,count;
 char *data;

 scanf("%d",&input);

 while(input!=0){
 
  count=0;
  parity=0;
  num=input;
  
  while(num>0){
   int i=num%BASE;
   *(data+count)=num%BASE;
   count++;
   (i==1) ? (parity+=1) : (parity+=0);
   num = num/BASE;
  }

  printf("The parity of ");  
  for(int j=count-1;j>=0;j--){
   printf("%d",*(data+j));
  }
  
  printf(" is %d (mod %d).\n",parity,BASE);
  scanf("%d",&input);
 }

 return 0;
}

[2015/07/20][update]利用Arithmetic shift算術位移的方式改寫]

1.取出最右邊的bit:利用位元運算子'&'

  bit = 01 & num; //get the rightest bit.

2.將原數字除以2:利用位元運算子 right shift右移'>>'

  num >>= 1; // num divided by 2

3.將原數字轉成二進位的數字

從link list的1號位置開始，逐一存放每個bit的值，若有8個bits，則存放在第1號到第8號位置。(第0號位置空下來)
實作方法:用count來計算位置，注意count的起始值、以及count++的順序擺放、列印二進位數值時for loop的起點與終點寫法。

 int input,num,bit,parity,count;
 int *binary;
 
  num=input;
  bit=parity=count=0;
  
  printf("The parity of ");
  while(num>0){
   bit = 01 & num;
   parity += bit;
   count++;
   *(binary+count)=bit;
   num >>= 1;
  }
  
  for(int i=count;i>0;i--)
   printf("%d",*(binary+i));
   
  printf(" is %d (mod 2).\n",parity);

4.讀取資料的中止條件:

讀取資料直到尾端:while(scanf("%d",&input)!=EOF){...}
若讀取到的數值為0，則使用"break;"跳出 while loop，接著來到 return 0; 程式終止。

 while(scanf("%d",&input)!=EOF){
 
  if(input==0)
   break;
               ......
 }
        return 0;

Code:

#include <stdio.h>

int main(void){
 
 int input,num,bit,parity,count;
 int *binary;
 
 while(scanf("%d",&input)!=EOF){
 
  if(input==0)
   break;
   
  num=input;
  bit=parity=count=0;
  
  printf("The parity of ");
  while(num>0){
   bit = 01 & num; //get the rightest bit.
   parity += bit; // calculate the parity.
   count++;
   *(binary+count)=bit;
   num >>= 1; // num divided by 2
  }
  
  for(int i=count;i>0;i--)
   printf("%d",*(binary+i));
   
  printf(" is %d (mod 2).\n",parity);
 }
 
 return 0;
}